Languages and Automata: Which Machine Goes With Which Grammar

Row by row, with the reason

Type 3 and the finite automaton

A type 3 production is A to aB: write one terminal, and hand over to one variable. A derivation therefore has exactly one variable in it at every step, sitting at the right hand end.

So the whole state of a derivation is which variable that is. A finite automaton's whole state is which state it is in. One variable per state and one production per transition, and the correspondence is immediate. Chapter 30 carries it out in both directions.

That is also the reason a finite automaton cannot count: a derivation with one variable can carry only a bounded amount of information forward, and a machine with finitely many states likewise.

Type 2 and the pushdown automaton

A type 2 production is A to gamma, where gamma may hold several variables. A derivation can therefore have many variables outstanding at once, and they must be dealt with in a definite order.

A leftmost derivation deals with the leftmost first, and the ones to its right wait. That is a stack: the variable most recently created and not yet expanded is the next one to be expanded, which is last in, first out. So the machine that matches a context free grammar is a machine with a stack, and the construction of chapter 58 makes the stack hold exactly the outstanding variables.

Type 1 and the linear bounded automaton

A type 1 production never shortens the string. So in a derivation of a string of length n, no sentential form is ever longer than n, because a form longer than n could never come back down.

That is a space bound, and it is the definition of the machine: a linear bounded automaton is a Turing machine whose head may not leave the portion of tape the input occupies. So the derivation and the machine are bounded by the same quantity, and chapter 61 uses that observation in both directions.

Type 0 and the Turing machine

No restriction on the grammar, no restriction on the machine's tape. A derivation may grow without bound and a Turing machine's tape may be used without bound.

Here the correspondence is not quite symmetric, and the asymmetry is the subject of Module 2. A type 0 grammar generates exactly the recursively enumerable languages, and a Turing machine accepts exactly the recursively enumerable languages, where accepting permits the machine to run for ever on a string not in the language. Chapter 27 said why that permission matters.

Four machines, four things they can and cannot do

The other half of the table is the languages that separate the rows, and these are the answers to "give an example".

Every one of those four is worked in this book, so the strictness of the hierarchy is demonstrated rather than asserted.

The correspondence made concrete: a machine and its grammar

The smallest row of the table, shown once here so the correspondence is not abstract. Chapter 30 gives the general construction.

Take a machine for the strings over {a, b} containing ab:

Accepts: ab, aab, abb, bab, abab

Rejects: ε, a, b, ba, aa, bb, baa

Now write the grammar mechanically: one variable per state, one production per transition, and an epsilon rule on each final state.

S->aA | bS
A->aA | bB
B->aB | bB | ε

Accepts: ab, aab, abb, bab, abab

Rejects: ε, a, b, ba, aa, bb

Read the two side by side. The row for S in the table becomes the two productions of S. The cell S on a holds A, and the production is S to aA: write the a that was read, and hand over to the variable for the state reached. The final state B gets an epsilon rule, because a run may stop there. Nothing else is needed, and the checker confirms the two accept exactly the same language.

Distinctions

What it does NOT mean

The correspondence is not an approximation. Each row is an if and only if with constructions in both directions, not a rough analogy.

A machine is not converted into a grammar by relabelling. The type 3 case looks like relabelling and is not: the epsilon rules on final states are a real step, and the type 2 case in chapter 59 is genuinely involved.

The four machines are not four programming languages. They are four amounts of memory, and the table above is really a table about memory.

A language having a grammar of one type does not stop it having a grammar of another. Every regular language has a context free grammar. What the table says is which type is the smallest that suffices.

The Turing machine row is not symmetric with the others. A Turing machine accepting a language may loop forever on strings outside it, which is chapter 27's distinction and has no analogue in the three rows below.

Quick revision

• Four rows: type 3 with the finite automaton, type 2 with the pushdown automaton, type 1 with the linear

bounded automaton, type 0 with the Turing machine. Each is an if and only if.

• The reason: a machine's memory matches the shape of its grammar's productions. One variable outstanding needs

one state; many outstanding need a stack; a non shortening grammar needs only as much tape as the input; an unrestricted grammar needs an unbounded tape.

• A type 3 derivation has exactly one variable at every step, at the right hand end.
• A leftmost derivation of a context free grammar handles outstanding variables last in first out, which is a

stack.

• A type 1 derivation never produces a form longer than the target string, which is the linear bound.
• The separating languages: strings ending in ab; a to the n b to the n; a to the n b to the n c to the n; the

halting language.

• To convert a finite automaton to a grammar: one variable per state, one production per transition, an epsilon

rule on each final state.

Test yourself

1. Give the four pairings. Type 3 with the finite automaton, type 2 with the pushdown automaton, type 1 with the linear bounded automaton, type 0 with the Turing machine, each characterising the regular, context free, context sensitive and recursively enumerable languages respectively.

2. Why does a context free grammar need a stack rather than finitely many states? Because a production may put several variables into the form at once, so a derivation has several outstanding variables and must return to them in a definite order. The most recently created is the next expanded, which is last in, first out.

3. Why is a non shortening grammar matched by a machine with a linear space bound? Because no sentential form in a derivation of a string of length n can be longer than n, since a longer form could never shrink back. So the derivation fits in the space the input occupies, which is what the machine's tape restriction says.

4. Convert this machine into a grammar: two states p start and q final, p on a to q, p on b to p, q on a to q, q on b to q. P->aQ | bP and Q->aQ | bQ | ε. One variable per state, one production per transition, and the epsilon rule on the variable for the final state.

5. Name the language separating each pair of adjacent classes. Strings ending in ab separates nothing below regular; a to the n b to the n is context free and not regular; a to the n b to the n c to the n is context sensitive and not context free; the halting language is recursively enumerable and not context sensitive.

6. In what way is the Turing machine row unlike the other three? Because a Turing machine accepting a recursively enumerable language may run for ever on a string outside it, so acceptance and decision come apart. In the three rows below, membership is decidable and the machine always answers.