Kleene's Theorem

We have shown how to convert a regular expression to an NFA; the proof that these represent the same language is straightforward (by induction). However, we have asserted that there is a correspondence in both directions; this is formalised in Kleene's Theorem:

KLEENE'S THEOREM, PART 1: To each regular expression there corresponds a NFA
Strategy: The corresponding NFA is the one constructed by Thompson's Algorithm; proof that it is equivalent is by induction over regular expressions.
Proof: Boring!

KLEENE'S THEOREM, PART 2: To each NFA there corresponds a regular expression
Strategy: Proof by induction over the states of the NFA (sort of).
The language represented by a NFA can be partitioned into the union of a number of smaller languages, each defined as follows:

Let the states of the NFA be numbered from 1 to $N$.
Let $p$ and $q$ be states, and let $J$ be a number such that $0 \leq J \leq N$.
Then:

$$L(p,q,J) = \left\{ \begin{array}{c} x \in \, \Sigma^* \, \mi... ...through no state numbered as high as $J$}\end{array} \right\}$$

Note that if $S$ is the start state, then the union of all $L(S,F,N+1)$ for all finish states $F$ is the language accepted by the NFA.

Equally, if we can show that $L(p,q,J)$ has a corresponding regular expression for all $p$, $q$ and $J$, we will have proved the theorem. The proof of this will proceed by induction over $J$.

Proof: (Kleene's Theorem, part 2)

• Base Case: $J = 1$
  We must be able to get from $p$ to $q$ without passing through any states; therefore either $p$=$q$, or we go directly in one transition from $p$ to $q$. The only strings that can be recognised in this case are $\varepsilon$ and single characters from $\Sigma$. The rules $R_1$ and $R_2$ give us a regular expression corresponding to these situations.

• Inductive Step: $J = K+1$
  The induction hypothesis is that for some $K$ such that $1 \leq K \leq N$, the language $L(p,q,K)$ has a corresponding regular expression. Now we must prove that, based on this assumption, $L(p,q,K+1)$ has a corresponding regular expression.

  Suppose the machine $L(p,q,K+1)$ consumes some string $x$; we must find a regular expression corresponding to $x$. Now suppose also that it passes through state $K$ on its way (if it doesn't, then $x$ is in $L(p,q,K)$, which has a corresponding regular expression by the induction hypothesis). Since the machine can ``loop'' on $K$ arbitrarily many times, we can split $x$ up into three substrings:

  a

  which moves the machine from state $p$ to state $K$

  b

  which causes the machine to ``loop'' on state $K$

  c

  which moves the machine from state $K$ to state $q$

  We note that while any of the above strings may cause us to start or finish at state $K$, none of them actually cause us to move through $K$. Thus we have:

  $a\; \in \; L(p,K,K)$

  $b\; \in \; L(K,K,K)$

  $c\; \in \; L(K,q,K)$

  By the induction hypothesis each of these have corresponding regular expressions, say A, B and C respectively, and thus the regular expression for $x$ is A(B*)C.

  Since our choice of $x$ was arbitrary, we have proved the theorem.

${\cal QED.}$