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

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

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

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

↑ "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

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]