Regular Sets and Regular Grammar: Kleene's Theorem Assembled

Step 4. And the grammar joins in. Chapter 30 converts a DFA into a right linear grammar and a right linear grammar into an NFA, both directly. So the fourth description sits on the same cycle.

Steps 1, 2 and 3 form a closed loop through three of the descriptions, and step 4 attaches the fourth to it. Since every arrow preserves the language, following the loop from any starting point and back proves all four descriptions equivalent.

The whole thing on one machine

Here is one language in all four descriptions, so the theorem is concrete rather than a diagram. The language is the strings over {a, b} ending in ab.

As a deterministic finite automaton:

Accepts: ab, aab, bab, abab, bbab

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

As a nondeterministic finite automaton, which needs only two states because it may guess where the final ab begins:

Accepts: ab, aab, bab, abab, bbab

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

As a regular expression:

(a + b)* a b

As a regular grammar, right linear, one variable per state of T1 and an epsilon rule on the final state:

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

Accepts: ab, aab, bab, abab, bbab

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

Four descriptions of one language, and three exact comparisons against the first. That is Kleene's theorem shown rather than stated, and every comparison is decided over every string there is.

What the theorem is worth

Three things follow, and each is used later.

A definition that does not depend on a description. "Regular" can be defined by any one of the four and means the same thing. So a proof may pick whichever description is convenient, and the proofs in this book do exactly that: chapter 38 proves closure under union from the expression and closure under complement from the machine, because each is easy in one description and awkward in the other.

A pipeline. A pattern written by a person becomes a machine a computer runs, and chapters 34, 17, 16 and 20 are the four stages of it. That is not an illustration; it is what happens when a regular expression is compiled.

A boundary. Because all four descriptions give the same class, a language shown to be outside the class by any method is outside all four. So when chapter 37 proves that a to the k followed by b to the k is not regular, it has proved at once that there is no machine for it, no expression for it, and no regular grammar for it. One proof, four consequences.

Where the name and the result came from

Kleene's RAND memorandum RM-704 is titled "Representation of Events in Nerve Nets and Finite Automata", and its summary states the question it sets out to answer: to what kinds of events can a nerve net respond by firing a certain neuron, and more generally, to what kinds of events can any finite automaton respond by assuming one of certain states. The summary dates the investigations it reports to August 1951.

Two things about that are worth noticing. The question is posed about nerve nets, following McCulloch and Pitts, so the finite automaton arrived in this literature as a model of a neuron and not of a computer. And the word Kleene used for what we call a language was event, which is why the class is called the regular sets rather than the regular languages in the older books, MU's included.

Chapter 26's Chomsky classification arrived from a third direction, linguistics, a few years later, and the identification of Kleene's regular events with Chomsky's type 3 grammars is the fourth arrow of this chapter. Three fields, three vocabularies, one class of languages.

Distinctions

What it does NOT mean

The four descriptions are not equally convenient. They describe the same class and are wildly different to work with, which is the table above.

The conversions do not preserve size. An expression becomes a machine about twice as large, and an NFA can become a DFA exponentially larger. Only the language is preserved.

A regular set is not a set of regular things. It is a language, and the older word for a language in this literature was event, which is where the mismatch of vocabulary comes from.

The theorem does not say the conversions are cheap. Chapter 16's bound is exponential and is achieved.

It does not extend upwards. Chapter 56 shows that the corresponding statement for pushdown automata fails, because a deterministic pushdown automaton is strictly weaker than a nondeterministic one.

Quick revision

• Four equivalent statements: accepted by a DFA; accepted by an NFA; denoted by a regular expression; generated by a

regular grammar. A language satisfying any is a regular set, also called a regular language.

• The equivalence of expressions and machines is Kleene's theorem.
• The proof is a cycle: expression to NFA by chapter 34; NFA to DFA by chapters 17 and 16; DFA to expression by

chapter 35; and the grammar joins the cycle by chapter 30, both ways.

• Every arrow preserves the language, so following the cycle proves all four equivalent.
• What it buys: a definition independent of description, a compilation pipeline, and one irregularity proof serving

all four descriptions.

• Kleene's memorandum RM-704 asked the question about nerve nets, and called a language an event, which is why the

class is called the regular sets in the older books.

• The conversions preserve the language and not the size; chapter 16's blow up is exponential and achieved.

Test yourself

1. State the four equivalent conditions. L is accepted by a DFA; L is accepted by an NFA; L is denoted by a regular expression; L is generated by a regular grammar. Any one implies all the others.

2. Which pair of them is Kleene's theorem? That a language is denoted by a regular expression exactly when it is accepted by a finite automaton, proved by chapter 34 in one direction and chapter 35 in the other.

3. Name the four constructions that close the cycle. Thompson's construction from an expression to an NFA with empty moves; the closure method removing the empty moves; the subset construction giving a DFA; and Arden's method or state elimination giving an expression back.

4. Why does one proof that a language is not regular settle four questions at once? Because the four descriptions define the same class, so a language outside the class has no machine of either kind, no expression and no regular grammar.

5. Convert this machine to a right linear grammar: p start, q final, p on a to q, p on b to p, q on a to q, q on b to p. P->aQ | bP and Q->aQ | bP | ε. One production per transition, and the epsilon rule on the variable for the final state.

6. Does the four part equivalence hold for pushdown automata? No. A deterministic pushdown automaton is strictly weaker than a nondeterministic one, so the analogue of the first two statements fails, and chapter 57 gives the witness language.