142 ~ Theory ofComputer Science
EXAMPLE 5.6
Consider a graph (i.e. transItIOn system), contammg a A-move, given in
Fig. 5.3. Obtain an equivalent graph (i.e. transition system) without A-moves.
Fig. 5.3 Finite automaton of Example 5.6.
Solution
There is a A-move from qo to Q3' There are two edges, one from q3 to q2 with
label °and another from (]3 to q4 with label!. We duplicate these edges from
qo. As qo is an initial state. q3 is made an initial state. The resulting transition
graph is given in Fig. 5.4.
o
__~:GO
Fig. 5.4 Transition system for Example 5.6, without A-moves.
5.2.2 NDFAs WITH A-MOVES AND REGULAR EXPRESSIONS
In this section, we prove that every regular expression is recognized by a
nondeterministic finite automaton (NDFA) with A-moves.
Theorem 5.2 (Kleene' s theorem) If R is a regular expression over L
representing L ~ L*. then there exists an NDFA M with A-moves such that
L = TUvll.
Proof The proof is by the pnnciple of induction on the total number of
characters in R. By 'character' we mean the elements of L, A, 0, * and +.
For example, if R =A + 10*11*0. the characters are A, +, 1, 0, *. 1, 1, *,
0, and the number of characters is 9.
Let L(R! denote the set represented by R.