Theorem 1 (Kleene).
Every regular language can be accepted by a finite automaton.
This is done inductively. We begin with atomic languages, and work our way up. First, note that , , where are accepted by the following finite automata respectively:
Next, suppose that and are regular languages, accepted by and respectively. Then
Since a regular language can only be built up this way, the proof is complete. ∎
Every language accepted by a finite automaton is regular.
Note that, using a state diagram of a finite automaton , a word accepted by 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
such that is regular, and each is constructed from by one of the regular operations (union, concatenation, and Kleene star), so that in the end, is also regular. Finally, we show that is a finite union of such ’s, and therefore is regular too.
Index the states of a finite automaton by positive integers: . Suppose . Define the language as follows: a word is in iff it is the label of a path from to such that each of the intermediate nodes on the path has an index at most . Now, fix , and do induction on .
is regular for any . This is so because a word in (if it is non-empty) has length at most 1, so that it is either in or . In any case, is regular.
If is regular, so is . Let be a path that begins at and ends at such that all of its intermediate nodes have indices no more than . Then either none of the nodes have indices more than , or is an intermediate node. In the later case, begins at , reaches for the first time, leaves , may or may not return to , until its last return (if it does return), and ends at . What we have just described can be put into an identity:
Since each of the languages on the right hand side is regular (as the last component is 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, is regular. Since , a finite union of regular languages, 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.
|Date of creation||2013-03-22 19:01:37|
|Last modified on||2013-03-22 19:01:37|
|Last modified by||CWoo (3771)|