The Chomsky Hierarchy
When Noam Chomsky first formalized generative grammars in 1956, he classified them into types now known as the Chomsky hierarchy. The difference between these types is that they have increasingly strict production rules and can express fewer formal languages. Two important types are context-free grammars (Type 2) and regular grammars (Type 3). The languages that can be described with such a grammar are called context-free languages and regular languages, respectively. Although much less powerful than unrestricted grammars (Type 0), which can in fact express any language that can be accepted by a Turing machine, these two restricted types of grammars are most often used because parsers for them can be efficiently implemented. For example, all regular languages can be recognized by a finite state machine, and for useful subsets of context-free grammars there are well-known algorithms to generate efficient LL parsers and LR parsers to recognize the corresponding languages those grammars generate.
Read more about this topic: Formal Grammar
Famous quotes containing the words chomsky and/or hierarchy:
“Unlimited economic growth has the marvelous quality of stilling discontent while maintaining privilege, a fact that has not gone unnoticed among liberal economists.”
—Noam Chomsky (b. 1928)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)