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:
“Suppose that humans happen to be so constructed that they desire the opportunity for freely undertaken productive work. Suppose that they want to be free from the meddling of technocrats and commissars, bankers and tycoons, mad bombers who engage in psychological tests of will with peasants defending their homes, behavioral scientists who can’t tell a pigeon from a poet, or anyone else who tries to wish freedom and dignity out of existence or beat them into oblivion.”
—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)