Chomsky hierarchy

Chomsky hierarchy . In Linguistics , Mathematics and Computing, it is said of the hierarchical system of definitions, devised by Noam Chomsky in 1956 at MIT to classify formal languages mathematically into four categories numbered 0 to 3 and formalizing mechanisms such as formal grammars , expressions and automata for recognize each type.

It is also known under the name of Chomsky Classification or Mathematical Hierarchy of Languages .

Chomsky’s Hierarchy.

Let be a language L defined by at least one grammar G that complies:

• If all the productions of Ghave the form or where A and B are nonterminal symbols and x is a terminal; so G is said to be a regular grammar and L is a regular or type 3 language .
• If all productions of Gare in the form where x is a combination of terminal and nonterminal symbols, then G is said to be a context-free grammar and L is a context-free or type 2 language .
• If the productions of G areof the form where A is any non-terminal symbol, x , y , and z are combinations of terminals and non-terminals, such that x and y can be empty strings; then G is said to be a context dependent grammar and L is a context dependent language or type 1 language .
• If none of the Lgrammars meet the above properties then it is said to be an unrestricted , recursively enumerable, or type 0 language .

From the conjunctual point of view, Chomsky’s hierarchy works as seen in the graph:

• .

So all type 3 (LR) languages ​​are also type 2 (LLC) and LLCs are type 1 (LDC) are type 0 (LSR or LRE).

Consequences.

Chomsky’s hierarchy not only provides a conjunctual ordering of languages, but also provides a classification mechanism based on characteristics related to the minimum grammatical forms of each particular language as well as deciding what type of minimum recognizers would be used to determine valid strings.

Facts that are sustained in the formalization of Alan Turing with his automata that emulated diverse algorithmic processes, models already demonstrated and accepted in the nascent community of specialists in computers and mathematics applied to computers. This contribution derived from the structuralist and mathematical vision of the moment of realization of this linguistic theory found its greatest application system in computer science and the development of theories and techniques of development of programming and specified languages ​​and the compilers and interpreters that they process them, providing them with a theoretical body and opening the doors to the great diversity of computer languages ​​that exist today.