Minimisation and limits

What an automaton remembers

The question

The same language is recognised by infinitely many automata. Among the complete DFAs that recognise it, is there a smallest one? Is it unique? And can we compute it?

To answer, we need to know what an automaton must remember from the beginning of a word in order to be able to answer at the end.

Residuals

The residual $u^{-1}L$ describes exactly what remains to be read to be accepted, once $u$ has been read. Two beginnings $u$ and $v$ that have the same residual are interchangeable: the rest of the word will never make it possible to tell them apart.

The link with states

In a complete DFA, all the words that lead to the same state $q$ have the same residual: it is the language $L_q$ of the words that lead from $q$ to a final state. So a complete DFA has at least as many states as $L$ has residuals.

Conversely, if $L$ has only finitely many residuals, we build a DFA whose states are the residuals:

• the initial state is $\varepsilon^{-1}L = L$;
• the letter $a$ leads from $R$ to $a^{-1}R$;
• the final states are the residuals that contain $\varepsilon$.

After reading $u$, this automaton is in state $u^{-1}L$, and it accepts if $\varepsilon \in u^{-1}L$, that is, if $u \in L$. It does recognise $L$, with the minimal number of states.

The empty residual, if there is one, corresponds to the sink state. If we prefer non-complete DFAs, we remove the sink, and the minimal automaton has one state fewer.

Computing the minimal automaton

The idea

Let us start from a complete DFA all of whose states are accessible. Two states $p$ and $q$ are equivalent if they have the same language: $L_p = L_q$. We can then merge them without changing the recognised language. By merging all the classes of equivalent states, we obtain the minimal automaton.

It remains to compute these classes. We cannot compare $L_p$ and $L_q$ directly: they are infinite sets. We proceed by successive refinements.

Moore's algorithm

We write $p \sim_k q$ if no word of length at most $k$ distinguishes $p$ and $q$: for every $w$ with $|w| \leq k$, $w$ leads from $p$ to a final state if and only if it leads from $q$ to a final state.

Each rank splits at least one class or stops the algorithm; there are at most $|Q|$ classes: we stop after at most $|Q|$ ranks.

An example

This complete DFA recognises the words that contain at least two $a$:

Rank 0: final $\{D, E\}$, non-final $\{A, B, C\}$.

Rank 1: for each state, we look at the rank-0 class of its successors by $a$ and by $b$.

$B$ separates from $A$ and $C$: three classes, $\{A, C\}$, $\{B\}$, $\{D, E\}$.

Rank 2: $A$ and $C$ both go to $B$ by $a$ and into $\{A, C\}$ by $b$; $D$ and $E$ stay in $\{D, E\}$. Nothing is split: we stop.

Three states, which remember “no $a$”, “one $a$”, “at least two $a$”. This is indeed the minimum: the three residuals $L$, $a^{-1}L$ and $(aa)^{-1}L = \Sigma^*$ are distinct.

The cost is of the order of $|Q|^2 \cdot |\Sigma|$. Hopcroft's algorithm, more subtle, does the same job in $|Q| \log |Q| \cdot |\Sigma|$.

Brzozowski's algorithm

There is another, surprising method. Writing $\mathrm{t}$ for transposition (chapter 6) and $\mathrm{d}$ for determinisation keeping only the accessible subsets (chapter 4):

is the minimal automaton of $L(A)$, without its sink if it has one, for every automaton $A$, even a nondeterministic one. We transpose, determinise, and do it again. The method is easy to program if we already have these two operations, but each determinisation can cost an exponential number of states.

A consequence

The minimal automaton is unique. To know whether two regular expressions are equivalent, we can therefore compute the minimal automaton of each and check that they are the same, up to the naming of states. This is a second answer to the question of chapter 2, after the synchronised product of chapter 6.

What an automaton cannot remember

Counting

Consider $L = \{a^n b^n \mid n \geq 0\}$: some $a$, then as many $b$. To recognise it, we must remember the number of $a$ read, however large it is. An automaton has only a finite number of states: intuitively, it cannot.

Residuals prove it. For $k \neq k'$, the word $b^k$ is in $(a^k)^{-1}L$ and not in $(a^{k'})^{-1}L$: the residuals $(a^k)^{-1}L$ are all different. $L$ has infinitely many residuals: it is not regular.

Residuals give an exact characterisation, but one has to guess the infinite family of residuals. The pumping lemma is another tool, often more direct.

The idea of the pumping lemma

Take an automaton with 10 states and an accepted word of 10 letters. The path that accepts it visits 11 states (the starting one, then one per letter). There are only 10 distinct states: at least one state $q$ is visited twice. The path therefore makes a loop at $q$.

Let us cut the word into three: $x$ leads from the initial state to $q$, $y$ makes the loop from $q$ to $q$, $z$ leads from $q$ to a final state.

The loop $y$ is not empty (at least one letter was read between the two visits to $q$). But $x$ or $z$ may be, if the loop is on the initial or the final state. And nothing forces us to go round the loop only once: $xz$, $xyyz$, $xyyyz$… are accepted too.

The statement

Proof. Let $A$ be a complete DFA that recognises $L$, and $k$ its number of states. Let $u \in L$ with $|u| \geq k$. The first $k$ letters of $u$ make the automaton visit $k + 1$ states: one of them, $q$, is visited twice. Call $x$ the beginning of $u$ up to the first visit to $q$, $y$ the part read between the two visits, $z$ the end. We have $y \neq \varepsilon$, $|xy| \leq k$, and the loop $y$ can be traversed as many times as we like, zero included. $\square$

The integer $k$ is the size of an automaton that recognises $L$. But the statement no longer mentions automata: it applies to every regular language, described in any way.

It is only an implication

For instance, $\{a^i b^j c^j \mid i \geq 1, j \geq 0\} \cup \{b^j c^k \mid j, k \geq 0\}$ satisfies the conclusion of the lemma with $k = 1$ (we always pump the first letter), and is not regular (its intersection with $ab^*c^*$ is $\{ab^jc^j\}$, which is not).

So the lemma is never used to show that a language is regular. It is used to show that a language is not, by contraposition: if, for every $k$, we find a long word that cannot be pumped, the language is not regular.

What about finite languages? They are regular, and satisfy the lemma without difficulty: it is enough to take $k$ larger than the longest word. No word of $L$ then has length at least $k$, and the condition is vacuous.

Showing that a language is not regular

A proof by the pumping lemma always has the same shape, which can be seen as a game against an adversary:

1. we assume $L$ regular; the adversary gives a $k$;
2. we choose a word $u \in L$ with $|u| \geq k$, cleverly;
3. the adversary cuts it as $xyz$ with $y \neq \varepsilon$ and $|xy| \leq k$; we must handle all possible cuts;
4. we find an $n$ such that $xy^nz \notin L$: contradiction.

Example: $a^n b^n$. Let $k$ be given. We choose $u = a^k b^k$. Since $|xy| \leq k$, $x$ and $y$ contain only $a$: $y = a^j$ with $j \geq 1$. Then $xz = a^{k-j}b^k$ has fewer $a$ than $b$: it is not in $L$. So $L$ is not regular.

Without the condition $|xy| \leq k$, we would have to examine where $y$ lies: among the $a$, among the $b$, or straddling both. In the first two cases, repeating $y$ breaks the balance; in the third, $xyyz$ contains a $b$ followed by an $a$. The condition $|xy| \leq k$ avoids this case analysis: this is why we choose a word whose beginning is well under control.

And parentheses?

$a^n b^n$ looks artificial. Let us replace $a$ with an opening parenthesis and $b$ with a closing one: $\texttt{(}^n\,\texttt{)}^n$. If the language $P$ of well-parenthesised words were regular, its intersection with $\texttt{(}^*\texttt{)}^*$ would be too (chapter 6). But this intersection is $\{\texttt{(}^n\texttt{)}^n\}$, which is not. So $P$ is not regular.

This is a real problem for the computer scientist: arithmetic expressions, the { } blocks of C, nested HTML tags all have this structure. Regular languages are not enough to describe the syntax of programming languages. This is why a compiler uses regular expressions to cut the text into words (lexical analysis), then more powerful grammars to check its structure (syntactic analysis, or parsing). The languages they describe, the context-free languages, are recognised by automata equipped with a stack: an unbounded memory, but one that can only be consulted from the top.