Chomsky hierarchy
The Chomsky hierarchy, sometimes known as the Chomsky-Schützenberger hierarchy, is a hierarchy of formal grammatical systems for describing various classes of languages; the hierarchy can apply to both human and computer languages. This hierarchy was first published in 1956 by Chomsky. [1] These grammatical systems were referred to by Chomsky as transformational grammars. Other linguists have developed variants; together these are known as generative grammars.
The basic idea of a generative grammar is to provide a set of rules which are capable of generating all possible grammatical sentences in some language; the rules must constrain the generation so that only grammatical sentences are generated. The rules can also be used in reverse to parse a sentence and check if it is grammatical.
Example of a very simple generative grammar
This very simple example can handle only a tiny subset of English and should not be taken seriously as a guide to English grammar or vocabulary. It is based on an example by David Crystal [2] and is a slight extension of an example on slide 9 of this lecture. [3]
Sentence -> NounPhrase VerbPhrase # A Sentence consists of a NounPhrase followed by a VerbPhrase NounPhrase -> Determiner Noun # A NounPhrase consists of a Determiner followed by a Noun VerbPhrase -> Verb NounPhrase # A VerbPhrase consists of a Verb followed by a NounPhrase Determiner -> a, the # A Determiner is one of: a or the Noun -> boy, girl, dog # A Noun is one of: boy or girl or dog Verb -> chased, heard, saw # A Verb is one of: chased or heard or saw
Notation used above:
- The symbol "->" means "can be replaced by".
- When there are several items on the right hand side separated by commas, any one of these items can be selected.
- The comments preceded by "#" are not part of the generative grammar, but hopefully will help folks understand the example a little better.
By making appropriate substitutions we can generate such sentences as:
- The dog chased a girl.
- The girl heard the dog.
- The boy saw a girl.
The stages in the generation of these examples are as follows:
- Sentence
- NounPhrase VerbPhrase
- Determiner Noun Verb NounPhrase
- Determiner Noun Verb Determiner Noun
By choosing the various options for Determiner, Noun, and Verb, we can generate 108 (= 2 * 3 * 3 * 2 * 3) different grammatical sentences.
Chomsky hierarchy
Chomsky defined 4 grammar levels; level 3 is a subset of level 2, which is a subset of level 1, which is a subset of level 0. The higher the level number, the simpler the generated language is, while the lower the level number the more difficult it is to parse a sentence in that language. [4] [5]
Level 0
Level 1
Level 2
Level 3
References
- ↑ Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory 2: 113–124. http://www.chomsky.info/articles/195609--.pdf. Retrieved 2012-04-08.
- ↑ Crystal, David (1987). The Cambridge Encyclopedia of Language. Cambridge University Press, page 97. ISBN 978052126438.
- ↑ Lecture notes: Formal Languages. Retrieved on 2012-04-07.
- ↑ Lecture notes: Languages & Grammars. Retrieved on 2012-04-07.
- ↑ The Chomsky Hierarchy. Retrieved on 2012-04-06.