Mathematical Foundation of Computer Science

DHARM

180 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

State

Input symbol

a

q 1

q

q

q

0

3

2

q

q

q

q

0

1

2

3

b

q

q

q

q

3
2
1
1
Fig. 7.15
Now we define the moves of DFA over the string abaabb (odd number of a’s and b’s both)
which must be acceptable or after reading the whole string automata reaches to the final state
{q 2 }.
So, compute δ$ (q 0 , abaabb) :
I.δ$ (q 0 , abaabb) = $δ (δ (q 0 , a), baabb)
= $δ (q 1 , baabb)[∴ δ (q 0 , a) = q 1 ]
II.δ$ (q 1 , baabb)= $δ (δ (q 1 , b), aabb)
= $δ (q 2 , aabb)[∴δ (q 1 , b) = q 2 ]
III.δ$ (q 2 , aabb)= $δ^ (δ (q 2 , a), abb)
= δ$ (q 3 , abb)[∴δ (q 2 , a) = q 3 ]
IV.δ$ ( q 3 , abb)= δ$ (δ (q 3 , a), bb)
= δ$ (q 2 , bb)[∴δ (q 3 , a) = q 2 ]
V.δ$ (q 2 , bb)= δ$ (δ (q 2 , b), b)
= δ$ (q 1 , b)[∴δ (q 2 , b) = q 1 ]
VI.δ$ (q 1 , b)= δ$ (q 1 , b.∈) = δ^ (δ (q 1 , b), ∈)
= δ$ (q 2 , ∈)[∴δ (q 1 , b) = q 2 ]
VII.δ$ (q 2 , ∈)= δ (q, ∈) [using Ist property of δ-head)
= {q 2 }
where {q 2 } is the accepted state of DFA M.

7.2.4 Language of a DFA

After knowing the behavior of the automata over an arbitrary string and finally over the set of
string we can easily define the language of a DFA. Let automata M be a DFA then language
accepted by M is LM where,
LM = {x / x ∈ Σ and δ$ (q 0 , x) ∈ F}
Alternatively, we say that any arbitrary string x from the set Σ will be the language of
DFA M if from initial state after reading the complete string x it reaches to final state. Now we
see that if Σ is the set of alphabet then set of all possible string formed over Σ is Σ. In the set
Σ there exists two possible class of languages, i.e.,

S*

LM

S*–LM