Chapter 5: Regular Sets and Regular Grammars Q 153
By applying Theorem 5.1. we obtain
q2 = (qi1)(1 + 011)* = q](l(l + 011)*)
From the ql-equation, we have
ql = qlO + q200 + C12010 + A
= q]O + q2(00 + 010) + A
= q]O + q]l(l + 011)* (00 + 010) + A
Again, by applying Theorem 5. L we obtain
ql = A(O + 1(1 + 011)* (00 + 010»*
q.. = Q201 = q 1 l(1 + 011)* 01
= (0 + 1(1 + 011)*(00 + 010»*(1(1 + 011)* 01)
5.2.5 CONSTRUCTION OF FINITE AUTOMATA EQUIVALENT
TO A REGULAR EXPRESSION
The method we are going to give for constructing a finite automaton
equivalent to a given regular expression is called the subset method which
involves two steps.
Step 1 Construct a transition graph (transition system) equivalent to the
given regular expression using A-moves. This is done by using Theorem 5.2.
Step 2 Construct the transition table for the transition graph obtained in
step L Using the method given in Section 5.2.3, construct the equivalent DFA.
We reduce the number of states if possible.
. EXAMPLE 5.13
Construct the finite automaton equivalent to the regular expression
(0 + 1)*(00 + 11)(0 + 1)*
Solution
Step 1 (Construction of transitIon graph) First of all we construct the
transition graph with A-moves using the constructions of Theorem 5.2. Then
we eliminate A-moves as discussed in Section 5.2. L
We start \vith Fig. 5.18(a).
V'le eliminate the concatenations in the given Le. by introducing new
vertices CJI and Ci2 and get Fig. 5.18(b).
We eliminate the'" operations in Fig. 5.18(b) by introducing two new
vertices Cis and CJ6 and the A-moves as shown in Fig. 5.18(c).
We eliminate concatenations and + in Fig. 5.18(c) and get Fig. 5.18(d).
We eliminate the A-moves in Fig.5.18(d) and get Fig. 5.18(e) which
gives the 1',TDFA equivalent to the gIven i.e.