1 50 ~ Theory of Computer Science
Solution
We can apply the above method directly since the graph does not contain the
A-move and there is only one initial state. We get the following equations for
q), Q2. q3' q4:
qj = q2b + q3a + A
q2 = qla
q3 = qjb
q4 = q2a + q3 b + q4 a + q4 b
As ql is the only final state and the qj-equation involves only q2 and q3' we
use only qr and qrequations (the q4-equation is redundant for our purposes).
Substituting for q2 and q3' we get
q 1 = q jab + q 1ba + A = q 1(ab + ba) + A
By applying Theorem 5.1, we get
ql = A(ab + ba)* = (ab + ba)*
As qj is the only final state, the strings accepted by the given finite automaton
are the strings given by (ab + ba)*. As any such string is a string of ab's,
and ba's, we get an equal number of a's and b's. If a prefix x of a sentence
accepted by the finite automaton has an even number of symbols, then it
should have an equal number of a's and b's since x is a substring formed by
ab's and ba's. If the prefix x has an odd number of symbols, then we can write
x as ya or yb. As y has an even number of symbols, y has an equal number
of a's and b's. Thus, x has one more a than b or vice versa.
EXAMPLE 5.10
DesClibe in English the set accepted by the finite automaton whose transition
diagram is as shown in Fig. 5.15.
Fig. 5.15 Finite automaton of Example 5.10.
Solution
We can apply the above method directly as the transition diagram does not
contain more than one initial state and there are no A-moves. We get the
following equations for qlo q2' q3'
qj = q10 + A
q2 = q 1 1 + q21
q3 = q20 + q3(O + 1)