Formal language
Language
Examples
Some examples of formal languages:
- the set of all words over [math]\displaystyle{ {a, b}\, }[/math]
- the set [math]\displaystyle{ \left \{ a^{n}\right\} }[/math], where [math]\displaystyle{ n\, }[/math] is a natural number and [math]\displaystyle{ a^n\, }[/math] means [math]\displaystyle{ a\, }[/math] repeated [math]\displaystyle{ n\, }[/math] times
- finite languages, such as [math]\displaystyle{ \{\{a,b\},\{a, aa, bba\}\}\, }[/math]
- the set of syntactically correct programs in a given programming language; or
- 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.
Other 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, chapter 6 Algebra of formalized languages.
- Template:Cite book
Other websites
- http://icalp06.dsi.unive.it/ 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