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:
“UG [universal grammar] may be regarded as a characterization of the genetically determined language faculty. One may think of this faculty as a ‘language acquisition device,’ an innate component of the human mind that yields a particular language through interaction with present experience, a device that converts experience into a system of knowledge attained: knowledge of one or another language.”
—Noam Chomsky (b. 1928)
“In the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (1916–1962)