From automata to expressions, Kleene's theorem

The question

In chapter 4, we showed $\mathrm{Rat} \subseteq \mathrm{Rec}$: every regular expression can be compiled into an automaton. The converse question arises: is every language recognised by an automaton regular? In other words, for a given automaton, is there an equivalent regular expression?

The answer is yes, and as in the previous chapter we shall prove it by giving an algorithm.

On examples

Let us start with small automata, whose expression can be read at a glance.

A single successful path, labelled $a$: the expression is $a$.

Two transitions in series: we concatenate them, $ac$.

A loop on the intermediate state: it can be taken any number of times, $ab^*c$.

Two parallel paths from 0 to 2: we take the union, $ab^*c + d$.

Let us look at what we did in the last case. To go from 0 to 2, we can go through 1 (reading $ab^*c$) or go directly (reading $d$). If we allow ourselves to label transitions with expressions instead of letters, we can draw:

We have just removed a state without changing the language. The algorithm consists in doing it again until only one transition remains.

State elimination

Generalised automata

An ordinary automaton is a generalised automaton: a letter is an expression, and so is $\varepsilon$. We allow ourselves one simplification: two transitions with the same origin and the same destination, $p \xrightarrow{e} q$ and $p \xrightarrow{f} q$, are merged into one, $p \xrightarrow{e + f} q$. So there is at most one transition per pair of states, and we write $e_{pq}$ for its label.

A unique initial and final state

We want to reach an automaton of the form $I \xrightarrow{e} F$, whose label $e$ will be the expression we are looking for. But an automaton can have several initial or final states. So we start by adding a new initial state $I$ and a new final state $F$, connected to the old ones by spontaneous transitions:

$I$ has no incoming transition, $F$ no outgoing one. The language has not changed. We are back to Thompson's invariant.

Removing a state

We want to remove a state $J$, other than $I$ and $F$, while preserving the language. For this, all the paths that went through $J$ must be able to go another way. A path that goes through $J$ arrives there from a predecessor $i$, loops there any number of times, and leaves towards a successor $k$.

We replace this passage with a direct detour from $i$ to $k$:

The convention simplifies things: if there was no transition from $i$ to $k$, $\emptyset + f \equiv f$; if there was no loop on $J$, $\emptyset^* \equiv \varepsilon$ and the factor disappears.

The algorithm

Each step removes a state, and the automaton is finite: the algorithm terminates. Each removal preserves the language: the result is correct. It is also called the state elimination method, or BMC.

The order in which the states are removed does not change the language, but it changes the expression obtained, sometimes a lot. A good heuristic is to remove first the state that creates the fewest detours: the one for which the product (number of predecessors) × (number of successors), not counting loops, is smallest.

A complete example

Let us find an expression for this automaton over $\{a, b, c\}$:

Normalisation. We add $I \xrightarrow{\varepsilon} 0$, $1 \xrightarrow{\varepsilon} F$ and $3 \xrightarrow{\varepsilon} F$.

Scores (predecessors × successors, without loops):

We remove 1. Predecessor 0; successors 3 and $F$. Two detours:

• $(0, 3)$: $\emptyset + a\,\varepsilon\,b = ab$;
• $(0, F)$: $\emptyset + a\,\varepsilon\,\varepsilon = a$.

New scores: 0 has successors 2, 3 and $F$, score 3; 2 keeps score 2; 3 has predecessors 0 and 2, successors 2 and $F$, score 4. We remove 2. Predecessors 0 and 3; successor 3; loop $a$.

• $(0, 3)$: $ab + b\,a^*\,a = ab + ba^+$;
• $(3, 3)$: $\emptyset + c\,a^*\,a = ca^+$. This is the case $i = k$: a loop on 3.

We remove 3 (score $1 \times 1$). Predecessor 0; successor $F$; loop $ca^+$.

• $(0, F)$: $a + (ba^+ + ab)(ca^+)^*\varepsilon = (ba^+ + ab)(ca^+)^* + a$.

We remove 0. A single detour, $(I, F)$: $\varepsilon \cdot ((ba^+ + ab)(ca^+)^* + a)$.

The automaton recognises

We can check it against the initial automaton: either we stop in 1 after $a$; or we reach 3 by $ab$ or by $ba^+$, then come back to it as many times as we like by $ca^+$.

The algorithm always works. But on a bigger automaton, the expression quickly becomes unreadable, and its size can grow exponentially with the number of states. Expressions are made to be written by humans; those produced by a machine are seldom pretty.

Another method: equations

We can also compute the expression by solving a system of equations. With each state $q$ we associate an unknown $X_q$: the language of the words that lead from $q$ to a final state. Each state gives an equation, which says how we can get out: “read $a$ and go to $q'$”, for each transition $q \xrightarrow{a} q'$, and “stop”, if $q$ is final.

For the second-to-last letter automaton, with transitions $0 \xrightarrow{a,b} 0$, $0 \xrightarrow{a} 1$, $1 \xrightarrow{a,b} 2$, and final state 2:

We substitute: $X_1 = a + b$, then $X_0 = (a + b)X_0 + a(a + b)$. The unknown appears on both sides. This is where the following lemma comes in.

Intuitively: a word of $X$ starts with some number of words of $K$, then ends with a word of $L$. The condition $\varepsilon \notin K$ ensures uniqueness; without it, $\Sigma^*$ would also be a solution of $X = \{\varepsilon\}X$.

Here, $K = a + b$ and $L = a(a + b)$: $X_0 = (a + b)^*a(a + b)$, and this is the expression of the language, since 0 is the initial state. The two methods give equivalent expressions, often different ones; the equation method lends itself well to computing by hand on small automata.

Kleene's theorem

We have just proved $\mathrm{Rec} \subseteq \mathrm{Rat}$. Together with chapter 4:

These are two identical sets, described in two ways of a different nature:

• regular expressions say what the language is: they are denotational;
• automata say how to recognise it: they are operational.

What they have in common is a finite memory. And we know how to go from one to the other in both directions, by algorithms.

In practice, we no longer need to distinguish $\mathrm{Rat}$ and $\mathrm{Rec}$: we speak of regular languages, and we choose the most convenient description for the question at hand. To show that a language is regular, it is enough to write an expression or to draw an automaton. To show a property of regular languages, we reason on expressions or on automata, whichever is simpler. This is what we do in the next chapter.