Formal language

In mathematics, computer science and linguistics, a formal language is one that has a particular set of symbols, and whose expressions are made according to a particular set of rules. The symbol ${\mathcal {L}}$ is often used as a variable for formal languages in logic.^[1]

Unlike natural languages, the symbols and formulas in formal languages are syntactically and semantically related to one another in a precise way.^[2] As a result, formal languages are completely (or almost completely) void of ambiguity.^[3]

Examples change

Some examples of formal languages include:

The set of all words over ${a,b}\,$
The set $\left\{a^{n}\right\}$ , where $n\,$ is a natural number and $a^{n}\,$ means $a\,$ repeated $n$ times
Finite languages, such as $\{\{a,b\},\{a,aa,bba\}\}\,$
The set of syntactically correct programs in a given programming language
The set of inputs upon which a certain Turing machine halts

Specification change

A formal language can be specified in a great variety of ways, such as:

Strings produced by some formal grammar (see Chomsky hierarchy)
Strings described or matched by a regular expression
Strings accepted by some automaton, such as a Turing machine or finite state automaton
Strings indicated by a decision procedure (a set of related yes/no questions) where the answer is 'yes'

Related pages change

Language for languages in general
Syntax for the form of a language in general
Semantics for the meanings in a language
Natural language for languages that are not formal
Computer language for application of formal languages in computing
Programming language for the application of formal languages to program computers

References change

↑ "Comprehensive List of Logic Symbols". Math Vault. 2020-04-06. Retrieved 2020-10-09.
↑ "Definition of formal language | Dictionary.com". www.dictionary.com. Retrieved 2020-10-09.
↑ "1.11. Formal and Natural Languages — How to Think like a Computer Scientist: Interactive Edition". runestone.academy. Retrieved 2020-10-09.

Other websites change

http://icalp06.dsi.unive.it/ Archived 2006-06-09 at the Wayback Machine ICALP 2006 33rd International Colloquium on Automata, Languages and Programming.
http://www.cs.auckland.ac.nz/CDMTCS/conferences/dlt/DLTConfSeries.html International Conferences on Developments in Language Theory

[1] "Comprehensive List of Logic Symbols". Math Vault. 2020-04-06. Retrieved 2020-10-09.

[2] "Definition of formal language | Dictionary.com". www.dictionary.com. Retrieved 2020-10-09.

[3] "1.11. Formal and Natural Languages — How to Think like a Computer Scientist: Interactive Edition". runestone.academy. Retrieved 2020-10-09.

[1]

[2]

[3]