Information and Control
In the context of formal languages, a grammar is a finite set of rules that can be written as functions converting one set of symbols into another. This definition of grammar is equivalent to Turing machines, in that the language produced by any grammar that can be so displayed can be recognized by a Turing machine (TM), and every set of strings that can be recognized by a given TM can be generated by such a grammar (This is equivalent to the Church-Turing Thesis). Chomsky defines a structure for displaying these grammars as a collection of replacement rules, where rules take the form φ → ψ, φ & ψ being strings. The rules operate on a start string #S# to produce all of the possible words in the language.
Grammar Axioms
Chomsky defined four axioms about these grammars:
- The operation &rarr is irreflexive. (This forbids useless and looping rules)
- A is non-terminal iff there are &phi, &psi, and &omega such that &phiA&psi&rarr&phi&omega&psi. (Defines non-terminal)
- The symbol # may not be used on the right side of a rule. (The # symbol defines the edges of the word, and is reserved)
- There is a finite set of pairs (&chi1, &omega1), ... (&chin, &omegan) such that for all &phi and &psi, &phi&rarr&psi iff there are &phi1, &phi2 and j&len such that &phi = &phi1&chij&phi2 and &psi = &phi1&omegaj&phi2. (There is a finite set of transition rules that gives a finite specification of the relation &rarr.)
Restrictions on Grammars / Language classes
Axioms
These axioms simply give the grammar a clear and definite form. They do not affect the languages which can be produced. Chomsky did, however propose three restrictions which do affect the possible languages.
- Restriction 1: If &phi&rarr&psi, then there are A, &phi1, &phi2 and &omega such that &phi = &phi1A&phi2, &psi = &phi1&omega&phi2, and &omega &ne I. (This restriction means that every rule, every (&chij, &omegaj) pair must convert a single non-terminal symbol into some non-empty string.)
- Restriction 2: If &phi&rarr&psi, then there are A, &phi1, &phi2 and &omega such that &phi = &phi1A&phi2, &psi = &phi1&omega&phi2, &omega &ne I, but A&rarr&omega. (This means that the limiting context (&phi1 and &phi2) of the transition be null.)
- Restriction 3: If &phi&rarr&psi, then there are A, &phi1, &phi2, &omega, a, and B such that &phi = &phi1A&phi2, &psi = &phi1&omega&phi2, &omega &ne I, A&rarr&omega, but &omega = aB or &omega = a. (This restriction means that only a single non-terminal may result from each transition, and that that non-terminal must be on the right side of the terminal character, of which there may be at most one.)
Separateness of Levels 0 and 1
These restrictions separate the class of phrase-structure grammars into 4 levels, with level 0 referring to the 'unrestricted' grammars allowed under the axioms alone, and the numbers of the other three levels referring to the restriction on it. Since each restriction contains the restriction before it, the layers are all nested, with 0 being the outermost layer.
Chomsky next shows that level 1 languages are not equivalent to level 0. Level 0 languages correspond to all turing machines, while every level 1 language is decidable. This is because restriction 1 never allows the string to shrink during generation. That means that a TM parsing a word from such a language can simply check the derivations of the grammar up to a length one greater than the word being compared. Thus, for a given word, it is possible to check all derivations that could possibly lead to that world in a finite amount of time, making it decidable. Since not all TMs are decidable, there are some level 0 languages that are not level 1.
Level 1 equivalency
Chomsky next provides a construction for the rule XB→BX. Although this rule is not allowed as a rule under the level 1 restriction, an equivalent multi-step rule can be created, so allowing it as a rule is merely a convenience and does not affect the classes of languages. Using that rule, Chomsky shows that the language of the form #ambnambnccc# is a level 1 language by constructing a grammar which produces it. He then uses an argument akin to the pumping lemma to show that that language cannot be produced by a type 2 grammar, so level 2 is not the same as level 1.
Counting Languages
Most of the rest of this paper is also in Sipser's book, with one very notable exception. Chomsky proposes an extension to the finite automata in the form of a finite number of counters, each of which can be incremented or decremented at each transition, and whose state can affect the transition. The set of languages produced by this machine is refered to as the counter languages. Clearly, it is at least as powerful as the finite automata, so all regular languages are also counter languages, and Chomsky sites proofs in his own and other papers that there are languages which are level 2 languages, but not counter languages.
Counter languages, however, are not nested like the other types. Not only can some level 2 languages be generated by the counting automata, but also the language #ambnambnccc#, which is level 1. Thus the set of counting languages does not form a simple level under the Chomsky heirarchy.
