Difference between revisions of "Chomsky hierarchy"
(add references) |
(expand description, add references, add example, add subheadings for future expansion) |
||
| Line 1: | Line 1: | ||
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 [[Noam Chomsky|Chomsky]]. | 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 [[Noam Chomsky|Chomsky]]. | ||
| − | <ref> | + | <ref>{{cite journal |
| − | {{cite web | + | | title = Three models for the description of language |
| + | | year = 1956 | ||
| + | | last = Chomsky | ||
| + | | first = Noam | ||
| + | | journal = IRE Transactions on Information Theory | ||
| + | | volume = 2 | ||
| + | | pages = 113–124 | ||
| + | | url = http://www.chomsky.info/articles/195609--.pdf | ||
| + | | accessdate = 2012-04-08 | ||
| + | }}</ref> | ||
| + | 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 grammatical. | ||
| + | |||
| + | ==Simple example== | ||
| + | The very simple example here is based on one by David Crystal. | ||
| + | <ref>{{cite book | ||
| + | | last = Crystal | ||
| + | | first = David | ||
| + | | title = The Cambridge Encyclopedia of Language | ||
| + | | publisher = Cambridge University Press | ||
| + | | year = 1987 | ||
| + | | isbn = 978052126438 | ||
| + | | pages = page 97 | ||
| + | }}</ref> 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. | ||
| + | |||
| + | ''Sentence'' -> ''NounPhrase'' ''VerbPhrase'' | ||
| + | ''NounPhrase'' -> ''Determiner'' ''Noun'' | ||
| + | ''VerbPhrase'' -> ''Verb'' ''NounPhrase'' | ||
| + | ''Determiner'' -> '''a''', '''the''' | ||
| + | ''Noun'' -> '''boy''', '''girl''', '''dog''' | ||
| + | ''Verb'' -> '''chased''', '''heard''', '''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. | ||
| + | |||
| + | ==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. | ||
| + | <ref>{{cite web | ||
| + | | url = http://www.cs.uaf.edu/2011/spring/cs331/lectures/cs331_20110124_grammar.html | ||
| + | | title = Lecture notes: Languages & Grammars | ||
| + | | accessdate = 2012-04-07}} | ||
| + | </ref> | ||
| + | <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> | ||
| − | <ref> | + | <ref>{{cite web |
| − | {{cite web | ||
| url = http://www.cs.princeton.edu/~rywang/99f126/slides/16th.pdf | | url = http://www.cs.princeton.edu/~rywang/99f126/slides/16th.pdf | ||
| title = Lecture notes: Formal Languages | | title = Lecture notes: Formal Languages | ||
| accessdate = 2012-04-07}} | | accessdate = 2012-04-07}} | ||
</ref> | </ref> | ||
| − | + | ||
| − | + | ===Level 0=== | |
| − | + | ||
| − | + | ===Level 1=== | |
| − | + | ||
| − | + | ===Level 2=== | |
| + | |||
| + | ===Level 3=== | ||
| + | |||
| + | |||
| + | |||
==References== | ==References== | ||
<references/> | <references/> | ||
Revision as of 13:42, 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 grammatical.
Simple example
The very simple example here is based on one 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.
Sentence -> NounPhrase VerbPhrase NounPhrase -> Determiner Noun VerbPhrase -> Verb NounPhrase Determiner -> a, the Noun -> boy, girl, dog Verb -> chased, heard, 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.
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.