Chomsky hierarchy
Jerarquía de Chomsky
- Date
- 1956 · confidence high
- Place
- Cambridge, Massachusetts, United States
- Credited to
- Noam Chomsky
- Field
- Knowledge & symbols
What was discovered
Chomsky classified formal grammars into four nested levels of increasing complexity — regular, context-free, context-sensitive and unrestricted — as part of his formalization of generative grammar. The hierarchy became a pillar of formal linguistics and computation theory, linking each grammar type to the class of automaton able to recognize it.
What it led to
- Design of programming languages and compilers
- Computability theory and automata
Built on
Made possible
- Government and binding theory1981
- Compilers based on context-free grammars