Difference between revisions of "Chomsky hierarchy"
Jump to navigation
Jump to search
(→Simple example: explain example) |
(reposition link, note how many sentences can be generated, clarify, add categories) |
||
| Line 13: | Line 13: | ||
These grammatical systems were referred to by Chomsky as ''transformational grammars''. Other linguists have developed variants; together these are known as ''generative grammars''. | 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 | + | 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== | ==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 | + | 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> and is a slight extension of an example on slide 9 of this lecture. |
| − | + | <ref>{{cite web | |
| − | + | | url = http://www.cs.princeton.edu/~rywang/99f126/slides/16th.pdf | |
| + | | title = Lecture notes: Formal Languages | ||
| + | | accessdate = 2012-04-07}} | ||
| + | </ref> | ||
''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' # A ''Sentence'' consists of a ''NounPhrase'' followed by a ''VerbPhrase'' | ''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'' | ''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'' | ''VerbPhrase'' -> ''Verb'' ''NounPhrase'' # A ''VerbPhrase'' consists of a ''Verb'' followed by a ''NounPhrase'' | ||
| − | ''Determiner'' -> '''a''', '''the''' # A ''Determiner'' is | + | ''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''' | ''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''' | ''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: | By making appropriate substitutions we can generate such sentences as: | ||
| Line 46: | Line 54: | ||
:''Determiner'' ''Noun'' ''Verb'' ''NounPhrase'' | :''Determiner'' ''Noun'' ''Verb'' ''NounPhrase'' | ||
:''Determiner'' ''Noun'' ''Verb'' ''Determiner'' ''Noun'' | :''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 hierarchy== | ||
| Line 58: | Line 68: | ||
| title = The Chomsky Hierarchy | | title = The Chomsky Hierarchy | ||
| accessdate = 2012-04-06}} | | accessdate = 2012-04-06}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ref> | </ref> | ||
| Line 78: | Line 83: | ||
==References== | ==References== | ||
<references/> | <references/> | ||
| + | |||
| + | [[category:linguistics]] | ||
| + | [[Category:Computer Science]] | ||
Revision as of 15:21, April 9, 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 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.