A containment hierarchy classifying formal grammars, and the languages they generate, into four nested classes of increasing expressive power, regular, context-free, context-sensitive and unrestricted, each requiring a more powerful class of automaton to recognize.
Facts
Core PrincipleA containment hierarchy of classes of formal grammars. 1 Connections
Sources
1. Wikipedia: Chomsky hierarchy
References, Chomsky 1956 entry
Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory.
Lead, first sentence
in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars.
In Group: Computability Theory and Formal Languages, Lead
The Chomsky hierarchy in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.