From expressions to automata

The compilation chain

We want a program that, for any regular expression, builds an efficient acceptor, that is, a DFA. We get there in three steps, each of them simple:

This is what lexical analyser generators such as lex or flex do, give or take a few optimisations: we give them expressions, they produce a DFA in the form of a table, and a C program that runs it.

First step: Thompson's construction

The idea

A regular expression is an inductive structure: three base cases ($\emptyset$, $\varepsilon$, a letter) and three constructions ($+$, product, star). We give an automaton for each base case and, for each construction, a way of assembling the automata of the subexpressions. Six cases in all, and we have an algorithm for every expression.

To keep the assemblies simple, all the automata built respect an invariant:

We draw such an automaton $A_e$, for an expression $e$, as a box of which we see only the entry $i_e$ and the exit $f_e$.

The base cases

For $\emptyset$: two states, and no transition. No path goes from $i$ to $f$, the language is empty.

For $\varepsilon$: one spontaneous transition.

For a letter $a$: one transition labelled $a$.

The constructions

Union. For $e + f$, a new initial state chooses, without reading anything, one of the two automata; a new final state joins them.

Product. For $ef$, we chain them: the exit of $A_e$ leads, without reading anything, to the entry of $A_f$. The initial state of $A_e$ and the final state of $A_f$ become those of the result.

Star. For $e^*$, we add a new initial state and a new final state. A spontaneous transition from $f_e$ to $i_e$ allows going round again; a transition from $i$ to $f$ allows going round zero times.

In all three cases, the result respects the invariant. It is what guarantees that the assemblies do not create spurious paths. For instance, for the star, if $i_e$ had incoming transitions, the loop $f_e \to i_e$ would allow taking them in the middle of a round, and recognising words that are not in $L(e)^*$.

Indeed, each base case creates two states, union and star add two, product adds none.

An example

For $aa + ab$, we build the automata of the four letters, chain them two by two for $aa$ and $ab$, then join everything.

Ten states: four letters and one $+$ make five times two states.

What we have proved

The construction works for every expression, by induction on its structure: in each of the six cases, $L(A_e) = L(e)$, provided it holds for the subexpressions. We have therefore proved:

And we have better than a proof of existence: an algorithm. But the automaton obtained is a poor program. It has many spontaneous transitions, and the machine can be “in several places at once”. It must be transformed.

Second step: eliminating spontaneous transitions

The principle

A spontaneous transition gives the machine a choice: take it or not, without reading anything. We want to remove them, compensating with ordinary transitions, so that the language does not change.

Let us go back to the automaton of $a^*b^*c^*$ from the previous chapter:

From state 0, we can read a $b$: by moving spontaneously to 1, then reading $b$. For this to remain possible without the spontaneous transition, we need a transition $0 \xrightarrow{b} 1$.

The algorithm

To eliminate the spontaneous transitions of an $\varepsilon$-NFA:

1. for each proper (non-spontaneous) transition $p \xrightarrow{a} q$, and for each state $r$ of $\mathrm{clo}^{-1}(p)$, add the transition $r \xrightarrow{a} q$;
2. make final every state from which a spontaneous path leads to a final state;
3. remove the spontaneous transitions;
4. trim, because some states may have become inaccessible.

Step 1 says: “if we could reach $p$ without reading anything and then read $a$, we can now read $a$ directly”. Step 2 says: “if we could finish by sliding to a final state, we can now finish here”.

On the example

The backward closures are $\mathrm{clo}^{-1}(0) = \{0\}$, $\mathrm{clo}^{-1}(1) = \{0, 1\}$, $\mathrm{clo}^{-1}(2) = \{0, 1, 2\}$.

• The transition $1 \xrightarrow{b} 1$ gives $0 \xrightarrow{b} 1$.
• The transition $2 \xrightarrow{c} 2$ gives $0 \xrightarrow{c} 2$ and $1 \xrightarrow{c} 2$.
• The transition $0 \xrightarrow{a} 0$ gives nothing new.

If we stop here, removing the spontaneous transitions, we get:

It is indeed an NFA. But it is not equivalent: it rejects $\varepsilon$, $a$ and $b$, which the original automaton accepted by sliding to 2 at the end. Step 2 is missing: 0 and 1 lead spontaneously to the final state 2, so they become final.

This automaton does recognise $a^*b^*c^*$.

We have thus shown that every $\varepsilon$-NFA has an equivalent NFA, with the same number of states. But the problem is not solved: the NFA obtained still has choices.

Third step: determinising

The problem

Let us go back to the automaton of the words whose second-to-last letter is $a$, that is, $(a + b)^*a(a + b)$:

It is an NFA. It is not deterministic: from 0, reading $a$, we can stay in 0 or go to 1. For this example, we could find a DFA by thinking about it. We want a mechanical procedure that works for every NFA.

The idea: follow the set of possible states

In chapter 3, to run an NFA, we followed the set of states the machine may be in. After $aaba$, for instance, it may be in 0 or in 1. Following this set is deterministic: to a set and a letter corresponds a single next set.

So it is enough to take these sets of states as the states of a new automaton. Since $Q$ is finite, there are only finitely many subsets of $Q$: the new automaton is finite.

The algorithm

In practice, we build only the accessible subsets: we start from $I$, compute its successors for each letter, then the successors of the new subsets, and so on until no new one appears. The computations are arranged in a table.

On the example

Only four subsets are accessible, out of the eight subsets of $\{0, 1, 2\}$.

Let us check: $aabaa$ leads from $\{0\}$ to $\{0, 1\}$, $\{0, 1, 2\}$, $\{0, 2\}$, $\{0, 1\}$, then $\{0, 1, 2\}$, which contains 2: accepted, the second-to-last letter is indeed $a$. $aaba$ stops in $\{0, 1\}$: rejected.

We can reinterpret this DFA: each state remembers the last two letters read. $\{0\}$: no $a$ among them; $\{0, 1\}$: they end with $ba$ (or the word is just $a$); $\{0, 1, 2\}$: $aa$; $\{0, 2\}$: $ab$. This is exactly the information needed to answer.

The result

The proof is the construction: after reading a word $u$, the state of $D$ is exactly the set of states $A$ may be in after $u$. So $D$ accepts $u$ if and only if one of these states is final, that is, if $A$ accepts $u$.

For an $\varepsilon$-NFA, we can either first eliminate the spontaneous transitions, or integrate them into the construction: each subset is replaced by its forward closure, the set of states reached from it by spontaneous transitions. Both methods give equivalent DFAs.

With Thompson's construction, we obtain:

The last inclusion is the subject of chapter 5. Once it is proved, all these classes will be equal: the three kinds of automata recognise exactly the same languages.

The cost

An NFA with $n$ states has $2^n$ subsets: the DFA can have up to $2^n$ states. This is not just a theoretical bound. For the language “the $k$-th letter from the end is an $a$”, i.e. $(a + b)^*a(a + b)^{k-1}$, the NFA has $k + 1$ states, and every equivalent DFA has at least $2^k$: it must remember the last $k$ letters, and there are $2^k$ possibilities.

In practice, such cases are rare: for the expressions one actually writes, the DFA usually stays of a size comparable to the NFA. And the cost is paid once, at construction time; the run itself remains linear in the length of the word.