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 ∅, {λ}, {a} where a∈Σ are accepted by the following finite automata respectively:
Next, suppose that L1 and L2 are regular languages, accepted by A1 and A2 respectively. Then
-
•
L1L2 is accepted by the finite automaton A1A2, the juxtaposition of automata A1 and A2;
-
•
L*1 is accepted by the finite automaton A*1, the Kleene star of automaton (http://planetmath.org/KleeneStarOfAnAutomaton) A1; and
-
•
L1∪L2 is accepted by A1∪A2, the union (http://planetmath.org/UnionOfAutomata) of A1 and A2.
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
L1⊆L2⊆⋯⊆Ln |
such that L1 is regular, and each Li+1 is constructed from Li by one of the regular operations (union, concatenation, and Kleene star), so that in the end, Ln 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: q1,…,qm. Suppose 1≤i,j,k≤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 qi to qj 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 non-empty) has length at most 1, so that it is either in Σ or λ. 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 qi and ends at qj 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 qk+1 is an intermediate node. In the later case, p begins at qi, reaches qk+1 for the first time, leaves qk+1, may or may not return to qk+1, until its last return (if it does return), and ends at qj. What we have just described can be put into an identity:
L(i,j,k+1)=L(i,j,k)∪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)=⋃{L(i,j,m)∣qi∈I,qj∈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 Σ*, 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 | 2013-03-22 19:01:37 |
Last modified on | 2013-03-22 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 |