Formal Language - Language-specification Formalisms

Language-specification Formalisms

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 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 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 automaton. Context-free grammars and regular grammars provide a good compromise between expressivity and ease of parsing, and are widely used in practical applications.