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 $ℒ$ is often used as a variable for formal languages in logic.

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

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

Further reading

• Template:Cite book
• Template:Cite book
• Template:Cite book

Other websites

• http://icalp06.dsi.unive.it/ Template:Webarchive 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