Jump to navigation Jump to search
In mathematics, a formal language is one that has a particular set of symbols that are made according to a particular kind of rule.
Examples[change | change source]
Some examples of formal languages:
- the set of all words over
- the set , where is a natural number and means repeated times
- finite languages, such as
- the set of syntactically correct programs in a given programming language; or
- the set of inputs upon which a certain Turing machine halts.
Specification[change | change source]
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 | change source]
- 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[change | change source]
- Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.CS1 maint: multiple names: authors list (link)
- Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics (3rd ed. ed.). PWN.CS1 maint: extra text (link), chapter 6 Algebra of formalized languages.
- Rozemberg, G. & Salomaa, A. (eds.) (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9.CS1 maint: multiple names: authors list (link) CS1 maint: extra text: authors list (link)
Other websites[change | change source]
- 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