Difference between revisions of "Chomsky hierarchy"
(reposition link, note how many sentences can be generated, clarify, add categories) |
(new section: Caution; also correct ISBN) |
||
| Line 11: | Line 11: | ||
| accessdate = 2012-04-08 | | accessdate = 2012-04-08 | ||
}}</ref> | }}</ref> | ||
| − | These grammatical systems were referred to by Chomsky as ''transformational grammars''. Other linguists have developed | + | These grammatical systems were referred to by Chomsky as ''transformational grammars''. Other linguists have since developed a variety of similar grammars; 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. | 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. | ||
| Line 23: | Line 23: | ||
| publisher = Cambridge University Press | | publisher = Cambridge University Press | ||
| year = 1987 | | year = 1987 | ||
| − | | isbn = | + | | isbn = 0-521-42443-7 |
| pages = page 97 | | pages = page 97 | ||
}}</ref> and is a slight extension of an example on slide 9 of this lecture. | }}</ref> and is a slight extension of an example on slide 9 of this lecture. | ||
| Line 55: | Line 55: | ||
:''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. | + | By choosing the various options for ''Determiner'', ''Noun'', and ''Verb'', we can, in this simple case, generate 108 (= 2 * 3 * 3 * 2 * 3) different grammatical sentences. |
| + | |||
| + | ==Caution== | ||
| + | While a generative grammar may produce sentences which are grammatically correct, there is no certainty that such sentences will actually mean anything. The classic example of such a meaningless sentence is from Chomsky's book | ||
| + | <ref>{{cite book | ||
| + | | last = Chomsky | ||
| + | | first = Noam | ||
| + | | title = Syntactic Structures | ||
| + | | year = 1957 | ||
| + | | publisher = Mouton | ||
| + | | location = The Hague/Paris | ||
| + | | pages = page 15 | ||
| + | | isbn = 3-11-017279-8 | ||
| + | }}</ref> with the sentence: | ||
| + | |||
| + | :"Colorless green ideas sleep furiously." | ||
| + | |||
| + | This example illustrates the difference between grammar/syntax and meaning/semantics. | ||
==Chomsky hierarchy== | ==Chomsky hierarchy== | ||
| Line 62: | Line 79: | ||
| url = http://www.cs.uaf.edu/2011/spring/cs331/lectures/cs331_20110124_grammar.html | | url = http://www.cs.uaf.edu/2011/spring/cs331/lectures/cs331_20110124_grammar.html | ||
| title = Lecture notes: Languages & Grammars | | title = Lecture notes: Languages & Grammars | ||
| − | | accessdate = 2012-04-07}} | + | | accessdate = 2012-04-07 |
| − | </ref> | + | }}</ref> |
<ref>{{cite web | <ref>{{cite web | ||
| url = http://adammikeal.org/courses/compute/Chomsky%20Presentation.pdf | | url = http://adammikeal.org/courses/compute/Chomsky%20Presentation.pdf | ||
| title = The Chomsky Hierarchy | | title = The Chomsky Hierarchy | ||
| − | | accessdate = 2012-04-06}} | + | | accessdate = 2012-04-06 |
| − | </ref> | + | }}</ref> |
===Level 0=== | ===Level 0=== | ||
Revision as of 18:38, April 10, 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 since developed a variety of similar grammars; 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, in this simple case, generate 108 (= 2 * 3 * 3 * 2 * 3) different grammatical sentences.
Caution
While a generative grammar may produce sentences which are grammatically correct, there is no certainty that such sentences will actually mean anything. The classic example of such a meaningless sentence is from Chomsky's book [4] with the sentence:
- "Colorless green ideas sleep furiously."
This example illustrates the difference between grammar/syntax and meaning/semantics.
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. [5] [6]
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 0-521-42443-7.
- ↑ Lecture notes: Formal Languages. Retrieved on 2012-04-07.
- ↑ Chomsky, Noam (1957). Syntactic Structures. The Hague/Paris: Mouton, page 15. ISBN 3-11-017279-8.
- ↑ Lecture notes: Languages & Grammars. Retrieved on 2012-04-07.
- ↑ The Chomsky Hierarchy. Retrieved on 2012-04-06.