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

 Further reading 




 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

Category:Mathematics
Category:Theoretical computer science
Category:Linguistics