Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 175

For example, following transition function
δ (q, a) = p ;
has the transition diagram

q p

a

then its transition table is

State Input symbol
a
q p
It shows automata is in state q and after reading (consuming) symbol a its state changes
to q.
Note. In the transition table the initial state is marked by an arrow and the final state is marked
by circle. For example, the DFA shown in fig 7.8 can be represented using transition table that is shown
below in Fig. 7.9.

State

Input symbol

a

q 1

q

q

q

0

3

2

q

q

q

q

0

1

2

3

a

q

q

q

q

3

2

1

1

Fig. 7.9

Example 7.4. Construct a DFA that accepts the string having the alphabet pattern 011.
Sol. We construct the DFA over set of alphabets Σ = {0, 1} by assuming q 0 is the initial state
then,
I. From the state q 0 onwards there must be a consumption of string 011 (which is
necessary a substring or substring containing pattern found in all acceptable string).

q 0 q 2 q 3

1

q 1

01

II. Any string starting with symbol 0 followed by any number of 0’s before the pattern

011 is accepted s.t. {011, 0011, 00011, ....}. So there must be a repetitive transition

arc in the state q 1 on symbol 0.

q 0 q 2 q 3

1

q 1

0

0 1

(from the state q 1 the last symbol seen was 0)