Chomsky hierarchy

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. 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.

Simple example

The very simple example here is based on one by David Crystal. 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.