Ì Exam ple 1.1.9: Construct a DFA which recognizes the set of all strings
on Σ = { , }
a b starting with the prefix ‘ab’.
Solu tion
Only two states (q 1 , q 2 ) are required to recognize ab, in addition to the input
state. One additional state called the “trap” state is also required.
Hence the DFA that recognizes the set of all strings on Σ = { , }
a b starting
with the prefix ‘ab’ is drawn above, where the automaton M is
M q q q q
q
({ , , , }, { , }, , { })
0
1
2
3
2
01 δ
with the state table diagram for δ as shown below.
δ
a
b
q 0
q 1
q 3
q 1
q 3
q 2
q 2
q 2
q 2
q 3
q 3
q 3
Fig. (b) State table dia gram
Ì Exam ple 1.1.10: Determine the DFA that will accept those words from
Σ = { , }
a b where the number of b’s is divisible by three. Sketch the state
table diagram of the finite Automaton M also.
Solu tion
The Finite Automaton M is M Q
q F
( , , , , )
Σ δ 0
with
Q
q q q
= { , , }
0
1
2
DFA and NFA
65
q 0
q 1
q 2
q 3
b
a,b
a
b
a
a,b
Fig. (a) DFA