152 g, Theory of Computer Science
Also,
q] = q10 + q30 + A = qIO + q200 + A
= q10 + (q 1 1(1 + 01)*)00 + A
= ql(O + 1(1 + 01)* 00) + A
Once again applying Theorem 5.1, we get
ql = NO + 1(1 + 01)* 00)* = (0 + 1(1 + 01)* 00)*
As ql is the only final state, the regular expression corresponding to the given
diagram is (0 + 1(1 + 01)* 00)*.
EXAMPLE 5.12
Find the regular expression corresponding to Fig. 5.17.
o
o
o
Gf------------i
o
Fig. 5.17 Finite automaton of Example 5.12.
Solution
There is only one initial state. and there are no A-moves. So, we form the
equations cOlTesponding to qj, q2, q3, q4:
ql = q10 + q30 + q40 + A
q2 = qll + q21 + q41
q3 = Q2 0
NO\v.
Thus. we are able to write q" q4 in terms of q2' Using the qTequation, we
get