Ì Exam ple 1.1.6: Obtain the DFA that accepts/recognizes the language
L(M) = {w | w ∈ {a, b, c}
* and w con tains the pat tern abac}
(Note: This is an application of DFA’s involving searching a text for a specified
pattern)
Solu tion
Let us begin by “hard coding” the pattern into the machines states as shown in
fig. (a) below.
As the pattern ‘abac’ has length four, there are four states required
in addition to one intial state q 0 , to remember the pattern. q 4 is the only
accepting state required and this state q 4 can be reached only after reading
‘abac’.
The complete DFA is as shown below in Fig. (b).
Ì Exam ple 1.1.7: Given Σ = { , }
a b , construct a DFA that shall recognize
the language L b ab m n
m
n
=
>
{
: ,
}
0 .
DFA and NFA
63
q 0
q 1
q 2
q 3
q 4
a
b
a
c
Input
Fig. (a)
q 0
q 1
q 2
q 3
b
b
b
b
a
a
a
a
q 0
q 1
q 2
q 3
a
q 4
b,c
c
a
b
a
c
b,c
b
a,b,c
a
Fig. (b)