Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 179

a

M

q

M

p

Þ

............y............ a ............y............

Here δ (q, a) = p and assume that after reading the remaining substring y automata
reaches to state r then δ$ (q, x) = r

⇒

a

M

r

............y............

(In this way automaton complete the transitions over input string x)

Example 7.9. A DFA M = ({q 0 , q 1 }, {a}, δ, q 0 , {q 1 }) has following transition characteristics:

q 0 q 1

a

a
Check behavior of the DFA over string aaa.
Sol. Assume autometer is in initial state {q 0 }. Now check the behaviour of DFA M over the
string aaa, i.e.

δ$ (q 0 , aaa) = $δ (δ(q 0 , a), aa) [Using II property of δ-head]

= $δ (q 1 , aa)[∴δ(q 0 , a) = q 1 ]

= $δ (δ(q 1 , a), a) [Using II property of δ-head]

= δ$ (q 0 , a)[∴δ(q 1 , a) = q 0 ]

= δ$ (q 0 , a. ∈)[∴ a. ∈ = a]

= $δ (δ(q 0 , a) [Using II property of δ-head]

= $δ(q 1 , ∈)[∴δ(q 0 , a) = q 1 ]

= {q 1 } [Using Ist property of δ-head]

Since state (q 1 ) is an accepted state, therefore string aaa is accepted by DFA M.

Example 7.10. Construct the DFA accepting the set of string having both odd number of a’s
and b’s.
Sol. The following DFA M accepts odd no. of a’s and b’s
where, M = ({q 0 , q 1 , q 2 , q 3 }, {a, b}, δ, q 0 , {q 2 }) and transition function shown in the transition
table (TT) Fig. 7.15.