If a string ends in a 0, it is “rejected” and “accepted” only if the string ends
in a 1. Therefore the language
L(M) = {w | w ends in a 1}.
Ì Exam ple 1.1.4: Design a DFA, the language recognized by the
Automaton being
L a b n
n
=
≥
{
:
}
0
Solu tion
For the given language L a b n
n
=
≥
{
:
}
0 , the strings could be b, ab, a
2 b, a
3 b, K .
Therefore the DFA accepts all strings consisting of an arbitrary number of
a’s, followed by a single b. All other input strings are rejected.
Ì Exam ple 1.1.5: Obtain the state table diagram and state transistion
diagram (DFA Schematic) of the finite state Automaton M
Q
= ( , , ,
Σ δ
q F
0 , ), where Q q q q q
= { , , , }
0
1
2
3 , Σ = { , },
a b q 0 is the initial state, F is the
final state with the transistion defined by
δ
δ
δ
δ
δ
( , )
( , )
( , )
( , )
( , )
q a q
q a q
q b q
q a q
q b q
0
2
3
1
2
3
1
3
0
1
=
=
=
=
=
δ
δ
δ
( , )
( , )
( , )
q b q
q a q
q b q
3
2
2
0
1
0
=
=
=
Solu tion
The State Table diagram is as shown below
δ
a
b
q 0
q 2
q 1
q 1
q 3
q 0
q 2
q 0
q 3
q 3
q 1
q 2
With the given definitions, the State Transition diagram/DFA Schematic is
shown on next page.
62
Theory of Automata, Formal Languages and Computation
q 0
q 2
q 1
b
a,b
a
a,b