Chapter 5: Regular Sets and Regular Grammars w 149
a
b
Fig. 5.13 Transition system of Example 5.8.
Solution
We can directly apply the above method since the graph does not contain any
A-move and there is only one initial state.
The three equations for q]. q2 and q3 can be written as
ql = q]a + q2b + A,
q2 = q]a + q2b + q3a .
q3 = q2a
It is necessary to reduce the number of unknowns by repeated substitution. By
substituting q3 in the q2-equation. we get by applying Theorem 5.1
q2 = q]a + q2b + q2aa
= qla + q2(b + aa)
= qla(b + aa)*
Substituting q2 in ql' we get
ql = qla + qla(b + aa)*b + A
= ql(a + a(b + aa)*b) + A
Hence,
ql = A(a + a(b + aa)*b)*
q2 = (a + a(b + aa)*b)* a(b + aa)*
q3 = (a + a(b + aa)*b)* a(b + aa)*a
Since q3 is a final state, the set of strings recognized by the graph is given by
(a + a(b + aa)*b)*a(b + aa)*a
EXAMPLE 5.9
Prove that the finite automaton whose transitIOn diagram is as shown in
Fig. 5.14 accepts the set of all strings over the alphabet {a, b} with an equal
number of a's and b's, such that each prefix has at most one more a than the
b's and at most one more b than the a's.
a
b
b
a
a,b
Fig. 5.14 Finite automaton of Example 5.9.