Editing Formal language (section)

== Language-specification formalisms ==

Formal languages are used as tools in multiple disciplines. However, formal language theory rarely concerns itself with particular languages (except as examples), but is mainly concerned with the study of various types of formalisms to describe languages. For instance, a language can be given as
* those strings generated by some [[formal grammar]];
* those strings described or matched by a particular [[regular expression]];
* those strings accepted by some [[Automata theory|automaton]], such as a [[Turing machine]] or [[finite-state automaton]];
* those strings for which some [[decision procedure]] (an [[algorithm]] that asks a sequence of related YES/NO questions) produces the answer YES.

Typical questions asked about such formalisms include:

* What is their expressive power? (Can formalism ''X'' describe every language that formalism ''Y'' can describe? Can it describe other languages?)
* What is their recognizability? (How difficult is it to decide whether a given word belongs to a language described by formalism ''X''?)
* What is their comparability? (How difficult is it to decide whether two languages, one described in formalism ''X'' and one in formalism ''Y'', or in ''X'' again, are actually the same language?).

Surprisingly often, the answer to these decision problems is "it cannot be done at all", or "it is extremely expensive" (with a characterization of how expensive). Therefore, formal language theory is a major application area of [[computability theory]] and [[computational complexity theory|complexity theory]]. Formal languages may be classified in the [[Chomsky hierarchy]] based on the expressive power of their generative grammar as well as the complexity of their recognizing [[automata theory|automaton]]. [[Context-free grammar]]s and [[regular grammar]]s provide a good compromise between expressivity and ease of [[parsing]], and are widely used in practical applications.