Martin

For every finite automaton $M=(Q,\Sigma,q_0,A,\delta)$, the language $L(M)$ is regular.

For states $p$ and $q$, we introduce the notation $L(p,q)$ for the language

If we can show that for every $p$ and $q$ in $Q$, $L(p,q)$ is regular, then it will follow that $L(M)$ is, because

and the union of a finite collection of regular languages is regular.

We will show that each language $L(p,q)$ is regular by expressing it in terms of simpler languages that are regular. Strings in $L(p,q)$ cause $M$ to move from $p$ to $q$ in any manner whatsoever. One way to think about simpler ways of moving from $p$ to $q$ is to think about the number of transitions involved; the problem with this approach is that there is no upper limit to this number, and so no obvious way to obtain a final regular expression. A similar approach that is more promising is to consider the distinct states through which $M$ passes as it moves from $p$ to $q$. We can start by considering how $M$ can go from $p$ to $q$ without going through any states, and at each step add one more state to the set through which $M$ is allowed to go. This procedure will terminate when we have enlarged the set to include all possible states.

If $x\in L(p,q)$, we say $x$ causes $M$ to go from $p$ to $q$ through a state $r$ if there are nonnull strings $x_1$ and $x_2$ such that $x=x_1x_2$, $\delta^*(p,x_1)=r$, and $\delta^*(r,x_2)=q$. In using a string of length 1 to go from $p$ to $q$, $M$ does not go through any state. (If $M$ loops from $p$ back to $p$ on the symbol $a$, it does not go through $p$ even though the string $a$ causes it to leave $p$ and enter $p$.) In using a string of length $n\ge2$, it goes through a state $n-1$ times, but if $n>2$ these states may not be distinct.

Now we assume that $Q$ has $n$ elements and that they are numbered from 1 to $n$. For $p,q\in Q$ and $j\ge0$, we let $L(p,q,j)$ be the set of strings in $L(p,q)$ that cause $M$ to go from $p$ to $q$ without going through any state numbered higher than $j$.

The set $L(p,q,0)$ is the set of strings that allow $M$ to go from $p$ to $q$ without going through any state at all. This includes the set of alphabet symbols $\sigma$ for which $\delta(p,\sigma)=q$, and in the case when $p=q$ it also includes the string $\Lambda$. In any case, $L(p,q,0)$ is a finite set of strings and therefore regular.

Suppose that for some number $k\ge0$, $L(p,q,k)$ is regular for every $p$ and every $q$ in $Q$, and consider how a string can be in $L(p,q,k+1)$. The easiest way is for it to be in $L(p,q,k)$, because if $M$ goes through no state numbered higher than $k$, it certainly goes through no state numbered higher than $k+1$. The other strings in $L(p,q,k+1)$ are those that cause $M$ to go from $p$ to $q$ by going through state $k+1$ and no higher-numbered states. A path of this type goes from $p$ to $k+1$; it may return to $k+1$ one or more times; and it finishes by going from $k+1$ to $q$ (see Figure 3.31). On each of these individual portions, the path starts or stops at state $k+1$ but doesn’t go through any state numbered higher than $k$.

Every string in $L(p,q,k+1)$ can be described in one of these two ways, and every string that has one of these two forms is in $L(p,q,k+1)$. The resulting formula is

We have the ingredients, both for a proof by mathematical induction that $L(p,q)$ is regular and for an algorithm to obtain a regular expression for this language. $L(p,q,0)$ can be described by a regular expression; for each $k<n$, $L(p,q,k+1)$ is described by the formula above; and $L(p,q,n)=L(p,q)$, because the condition that the path go through no state numbered higher than $n$ is no restriction at all if there are no states numbered higher than $n$. As we observed at the beginning of the proof, the last step in obtaining a regular expression for $L(M)$ is to use the $+$ operation to combine the expressions for the languages $L(q_0,q)$, where $q\in A$.

Let $M$ be the finite automaton pictured in Figure 3.33.

If we let $r(i,j,k)$ denote a regular expression corresponding to the language $L(i,j,k)$ described in the proof of Theorem 3.30, then $L(M)$ is described by the regular expression $r(M)$, where

We might try calculating this expression from the top down, at least until we can see how many of the terms $r(i,j,k)$ we will need that involve smaller values of $k$. The recursive formula in the proof of the theorem tells us that

Applying the formula to the expressions $r(i,j,2)$ that we apparently need, we obtain

At this point it is clear that we need every one of the expressions $r(i,j,1)$, and we now start at the bottom and work our way up. The three tables below show the expressions $r(i,j,0)$, $r(i,j,1)$, and $r(i,j,2)$ for all combinations of $i$ and $j$. (Only six of the nine entries in the last table are required.)

For example,

The terms required for the final regular expression can now be obtained from the last table. As you can see, these expressions get very involved, even though we have already made some attempts to simplify them. There is no guarantee that the final regular expression is the simplest possible (it seems clear in this case that it is not), but at least we have a systematic way of generating a regular expression corresponding to $L(M)$.