SkipCaptcha
265
edits
Changes
expand description, add references, add example, add subheadings for future expansion
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/>