Solu tion
M does not accept specified language, as long as three consecutive b’s have not
been read.
It should be noted that
(i) M is in state q i (where i = 0,1, or 2) immediately after reading a run
of i consecutive b’s that either began the input string or was
preceded by an ‘a’.
(ii) If an ‘a’ is read and M is in state, q 0 , q 1 , or M returns to its initial
state q 0 .
q 0 , q 1 and q 2 are “Final states” (as given in the problem). Therefore any input
string not containing three consecutive b’s will be accepted.
In case we get three consecutive b’s then the q 3 state is reached (which is
not final state), hence M will remain in this state, irrespective of any other
symbol in the rest of the string. This state q 3 is said to be “dead state” or M is
said to be “trapped” at q 3 .
The DFA schematic is shown below based on the discussion above.
Ì Exam ple 1.1.2: Determine the DFA schematic for M
Q
q F
= ( , , , , )
Σ δ
where Q = {q 1 , q 2 , q 3 }, Σ = {0,1}, q 1 is the start state, F = {q 2 } and δ is
given by the table below.
Ini tial state
q
Sym bol
σ
Final state
δ σ
( , )
q
q 1
0
q 1
q 1
1
q 2
q 2
0
q 3
q 2
1
q 2
q 3
0
q 2
q 3
1
q 2
Also determine a Language L recognized by the DFA.
60
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 2
q 3
a
a
b
b
b
b
a
a
Fig. Finite Auto maton with four states