Difference between revisions of "Chomsky hierarchy"
m (grammar) |
(→Simple example: explain example) |
||
| Line 15: | Line 15: | ||
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 also constrain 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. | 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 also constrain 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. | |
<ref>{{cite book | <ref>{{cite book | ||
| last = Crystal | | last = Crystal | ||
| Line 25: | Line 25: | ||
| isbn = 978052126438 | | isbn = 978052126438 | ||
| pages = page 97 | | pages = page 97 | ||
| − | }}</ref> | + | }}</ref> |
| − | ''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' | + | 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. |
| − | ''NounPhrase'' -> ''Determiner'' ''Noun'' | + | |
| − | ''VerbPhrase'' -> ''Verb'' ''NounPhrase'' | + | ''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # A ''Sentence'' consists of a ''NounPhrase'' followed by a ''VerbPhrase'' |
| − | ''Determiner'' -> '''a''', '''the''' | + | ''NounPhrase'' -> ''Determiner'' ''Noun'' # A ''NounPhrase'' consists of a ''Determiner'' followed by a ''Noun'' |
| − | ''Noun'' -> '''boy''', '''girl''', '''dog''' | + | ''VerbPhrase'' -> ''Verb'' ''NounPhrase'' # A ''VerbPhrase'' consists of a ''Verb'' followed by a ''NounPhrase'' |
| − | ''Verb'' -> '''chased''', '''heard''', '''saw''' | + | ''Determiner'' -> '''a''', '''the''' # A ''Determiner'' is either '''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''' | ||
By making appropriate substitutions we can generate such sentences as: | By making appropriate substitutions we can generate such sentences as: | ||
| Line 38: | Line 40: | ||
:The girl heard the dog. | :The girl heard the dog. | ||
:The boy saw a girl. | :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'' | ||
==Chomsky hierarchy== | ==Chomsky hierarchy== | ||
Revision as of 22:30, April 8, 2012
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 also constrain 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]
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.
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 either 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
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
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. [3] [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: Languages & Grammars. Retrieved on 2012-04-07.
- ↑ The Chomsky Hierarchy. Retrieved on 2012-04-06.
- ↑ Lecture notes: Formal Languages. Retrieved on 2012-04-07.