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 grammatically correct 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, and variations on that example will be used to illustrate new ideas. 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.

A list of all the terminal items is effectively the vocabulary from which sentences are built.

Linguists have developed various classes of grammars by using constraints to govern what sort of rules can be used for any particular grammar.

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

This means that a Sentence is either a NounPhrase followed by a VerbPhrase or a NounPhrase followed by a VerbPhrase followed by and followed by a NounPhrase followed by a VerbPhrase. In addition to the shorter sentences already discussed, this could also 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), though some of these may not be very meaingful.

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 in this example generate exactly the same sentences.

Sentence   ->  NounPhrase VerbPhrase, Sentence and NounPhrase VerbPhrase 

The distinction between left- and right-recursive grammars 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

By imposing different constraints as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult. The following table provides a summary, which is then explained further in the subsequent subsections.

In the late 1950's, John Backus and Peter Naur independently developed a notation for describing programming languages (specifically for Algol 60 in fact). This notation is known as Backus Naur Form (or BNF) and turns out to be equivalent to Chomsky's grammar number two (context-free grammar).

Chomsky number	linguistic name	Rule constraints	Recogniser+	Notes
0	recursively enumerable	[anything] -> [anything]	Turing machine	most human languages
1	context-sensitive	X A Y -> X [anything] Y	linear bounded automaton	X and Y provide the context in which A can be transformed
2	context-free	A -> [anything]	non-deterministic push-down automaton	syntax analysis for most programming languages
3	regular	A -> [nothing] A -> xyz A -> xyz B	finite automaton or finite state machine	lexical analysis (combining characters into words/tokens)

+ The recogniser column indicates the type of mathematical or computer science theoretical model needed to recognise that a sentence belongs to a language, essentially by applying the transformation rules in reverse to work backwards from the actual words in order to finish up with a sentence (in programming languages the starting concept is usually a program). A finite automaton uses only a small fixed amount of memory, operates in time proportional to the length of the input, and always reaches a decision, while a Turing machine may use an infinite amount of memory and time and may fail to reach a decision (may never stop).

The descriptions of the various Chomsky levels which follows is presented in reverse order, so as to work up from a simple case to a rather complicated case.

Level 3: regular grammar

In its simplest form a Word consists of a sequence of one or more letters. In the regular grammar which follows the two possible transformations of PartWord are placed on separate lines instead of on one line separated by a comma. We ignore capital letters for now. PartWord is recursively defined and may be transformed into nothing.

Word     -> Letter PartWord
PartWord -> [nothing]
PartWord -> Letter PartWord
Letter   -> a, b, ... z

For one-letter words we expand as:

Word -> Letter PartWord -> Letter [nothing] -> Letter

For two-letter words we expand as:

Word -> Letter PartWord -> Letter Letter PartWord -> Letter Letter [nothing] -> Letter Letter