Kleene’s theorem
Theorem 1 (Kleene).
The best way to prove this theorem is to visualize a finite automaton as a directed graph^{} (its state diagram^{}). We prove sufficiency and necessity separately.
Lemma 1.
Every regular language can be accepted by a finite automaton.
Proof.
This is done inductively. We begin with atomic languages, and work our way up. First, note that $\mathrm{\varnothing}$, $\{\lambda \}$, $\{a\}$ where $a\in \mathrm{\Sigma}$ are accepted by the following finite automata respectively:
Next, suppose that ${L}_{1}$ and ${L}_{2}$ are regular languages, accepted by ${A}_{1}$ and ${A}_{2}$ respectively. Then

•
${L}_{1}{L}_{2}$ is accepted by the finite automaton ${A}_{1}{A}_{2}$, the juxtaposition of automata ${A}_{1}$ and ${A}_{2}$;

•
${L}_{1}^{*}$ is accepted by the finite automaton ${A}_{1}^{*}$, the Kleene star of automaton (http://planetmath.org/KleeneStarOfAnAutomaton) ${A}_{1}$; and

•
${L}_{1}\cup {L}_{2}$ is accepted by ${A}_{1}\cup {A}_{2}$, the union (http://planetmath.org/UnionOfAutomata) of ${A}_{1}$ and ${A}_{2}$.
Since a regular language can only be built up this way, the proof is complete^{}. ∎
Lemma 2.
Every language accepted by a finite automaton is regular.
Note that, using a state diagram of a finite automaton $A$, a word accepted by $A$ is the label of a path that begins from one of the starting nodes and ends in one of the final nodes. In the proof, we build a sequence of languages
$${L}_{1}\subseteq {L}_{2}\subseteq \mathrm{\cdots}\subseteq {L}_{n}$$ 
such that ${L}_{1}$ is regular, and each ${L}_{i+1}$ is constructed from ${L}_{i}$ by one of the regular operations^{} (union, concatenation^{}, and Kleene star), so that in the end, ${L}_{n}$ is also regular. Finally, we show that $L(A)$ is a finite union of such $L(n)$’s, and therefore $L(A)$ is regular too.
Proof.
Index the states of a finite automaton $A$ by positive integers: ${q}_{1},\mathrm{\dots},{q}_{m}$. Suppose $1\le i,j,k\le m$. Define the language $L(i,j,k)$ as follows: a word is in $L(i,j,k)$ iff it is the label of a path from ${q}_{i}$ to ${q}_{j}$ such that each of the intermediate nodes on the path has an index at most $k$. Now, fix $i,j$, and do induction^{} on $k$.

1.
$L(i,j,0)$ is regular for any $i,j$. This is so because a word in $L(i,j,0)$ (if it is nonempty) has length at most 1, so that it is either in $\mathrm{\Sigma}$ or $\lambda $. In any case, $L(i,j,0)$ is regular.

2.
If $L(i,j,k)$ is regular, so is $L(i,j,k+1)$. Let $p$ be a path that begins at ${q}_{i}$ and ends at ${q}_{j}$ such that all of its intermediate nodes have indices no more than $k+1$. Then either none of the nodes have indices more than $k$, or ${q}_{k+1}$ is an intermediate node. In the later case, $p$ begins at ${q}_{i}$, reaches ${q}_{k+1}$ for the first time, leaves ${q}_{k+1}$, may or may not return to ${q}_{k+1}$, until its last return (if it does return), and ends at ${q}_{j}$. What we have just described can be put into an identity^{}:
$$L(i,j,k+1)=L(i,j,k)\cup L(i,k+1,k)L{(k+1,k+1,k)}^{*}L(k+1,j,k).$$ Since each of the languages on the right hand side is regular (as the last component^{} is $k$ in each case), the language on the left hand side is reqular (as it is obtained by performing regular operations on regular languages).
In particular, $L(i,j,m)$ is regular. Since $L(A)=\bigcup \{L(i,j,m)\mid {q}_{i}\in I,{q}_{j}\in F\}$, a finite union of regular languages, $L(A)$ is regular as well. ∎
Remark. Kleene’s theorem can be generalized in at least two ways. By realizing that an automaton is just a directed graph whose edges are labeled by elements of ${\mathrm{\Sigma}}^{*}$, a finitely generated^{} free monoid, one may define a finite automaton over an arbitrary monoid. For more details, see this entry (http://planetmath.org/AutomatonOverAMonoid). The other is to generalize the notion of a word from finite to infinite^{}, and modify the notion of acceptance so infinite words may be accepted.
Title  Kleene’s theorem 

Canonical name  KleenesTheorem 
Date of creation  20130322 19:01:37 
Last modified on  20130322 19:01:37 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03D10 
Classification  msc 68Q05 
Classification  msc 68Q42 
Related topic  RegularLanguage 