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 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 and is a slight extension of an example on slide 9 of this lecture.

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, just 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 appropriate selection of words to substitute for Determiner, Noun, and Verb we can produce the 3 example sentences above.

The simple grammar defines a few words which can be substituted for Determiner, Noun, and Verb. There are two possibilities for Determiner, three for Noun, and three for Verb, with both Determiner and Noun appearing twice in the expansion. Hence the total number of grammatical sentences which can be generated by this simple grammar is 108 (= 2 * 3 * 3 * 2 * 3). In this particular case the possible words have been carefully chosen so that all of these 108 sentences also actually mean something.

Note that the use of italics and boldface in this example is merely a convenient way of indicating the difference between items which can be expanded further (e.g. concepts such as NounPhrase) and items which can not be expanded further (e.g. words such as girl). In the linguistic literature, items which can be expanded further are referred to as 'non-terminal' items, while items which can't be expanded further are known as 'terminal' items.

The 'comma' notation for alternatives is a form of shorthand. In some formulations this would be shown as several separate rules, so that:

  Determiner ->  a, the 

could be shown as two rules:

  Determiner ->  a
  Determiner ->  the 

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 with the sentence:

"Colorless green ideas sleep furiously."

This example illustrates the difference between grammar/syntax and meaning/semantics.

Another problem when analysing a sentence is that many English words have multiple meanings, so that there may be more than one way to interpret a sentence. A simple example is the sentence:

"Time flies."

Is this an instruction to check how fast flies are flying, or an indication that time appears to be passing quickly?

A varied and entertaining selection of such ambiguities has been compiled by Jeff Gray.

Formal grammar

Note: this section and subsequent sections are, by necessity, slightly more technical/formal than the earlier parts of this article. Make sure that you understand the 'Simple example' above before proceeding further, since references will be made to that example to help explain the technicalities. An attempt has been made to avoid formal linguistic abbreviations and unexplained jargon.

A formal generative grammar has four components (see slide 19 of this lecture ):

1. a finite number of non-terminal concepts (e.g. VerbPhrase in the example, or anything else in italics),
2. a finite number of terminal items (e.g. girl in the example, or anything else in bold-face).
3. a finite set of rules for transforming non-terminal items (e.g. the example has 6 rules).
4. a single starting point (e.g. Sentence in the example).

Notes:

Any item which appears on the left-hand side of a transformation rule is non-terminal since it can be replaced by something else; apart from the starting point, all other non-terminals must also appear somewhere on the right-hand side of transformation rule.

An item which appears only on the right-hand side of a transformation rule is a terminal item, since it can not be transformed further.

Many different classes of generative grammars can be obtained by varying the constraints which govern what sort of rules can be used; the Chomsky hierarchy, detailed below, is obtained by modifying the constraints.

Changing the rules

An relatively small change to even a single rule can make a large change in the language which can be generated. For example, change the first rule in the simple example to read:

Sentence   ->  NounPhrase VerbPhrase, NounPhrase VerbPhrase and NounPhrase VerbPhrase

In addition to the shorter sentences already discussed, this could generate a sentence such as: "A dog saw a girl and the dog chased the girl". The total number of grammatically-correct sentences which can be generated by this modified grammar is now 11,772 (108 + 108*108).

Towards infinity

A significantly different rule change can have an astounding effect. Consider changing the first rule to read:

Sentence   ->  NounPhrase VerbPhrase, NounPhrase VerbPhrase and Sentence

This can generate a potentially infinite number of sentences (any number of these five-word sentences linked by and). This is an example of what is known as a recursive definition, whereby a Sentence is partially defined in terms of itself. In such a recursive rule there must be at least one transformation option which does not involve Sentence, otherwise the transformation could never stop.

The above change is known as right-recursive; a left-recursive formulation is also possible, and can generate exactly the same sentences.

Sentence   ->  NounPhrase VerbPhrase, Sentence and NounPhrase VerbPhrase 

The distinction between left- and right-recursive becomes important when trying to parse/analyse a sentence; some types of parser work best with left-recursive grammars, while other types work best with right-recursive grammars. This distinction is particularly relevant in connection with compiling or translating a program written in some high-level programming language so that it can be used on a computer.

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.