Mathematical Foundation of Computer Science

DHARM

176 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

III. Similarly, any string starting with symbol 1 and followed by any number of 1’s be-

fore the pattern 011 is accepted s.t. {1011, 11011, 111011,......}. So there must be

repetitions of symbol 1 on state q 0.

q 0 q 2 q 3

1

q 1

0 1

1

IV. Combining II and III we get the following DFA.

q 0 q 2 q 3

1

q 1

0

0 1

1

V. If the string containing 01 followed by pattern 011, then from the sate q 2 there is an

arc return to state q 1 on input symbol 0, so the automata reach to its accepted state

q 3 after reading the pattern 011.

q 0 q 2 q 3

1

q 1

0

0 1

1

0

(from the state q 2 last two symbol seen were 01)

VI. After the pattern 011 the string might contain any number of 0’s or/and 1’s, for that

there is a repetitive arc on state q 3 over symbol 0 or 1. (Fig. 7.10)

q 0 q 2 q 3

1

q 1

0

0 1

1

0

0, 1

Fig. 7.10
In this automaton we observed that there is one and only one exit on each symbol from
each state. Due to this fact automaton is ‘Deterministic’.
Finally, the DFA M = ({q 0 , q 1 , q 2 , q 3 }, {0, 1}, δ, q 0 , {q 3 }); where δ’s are shown in the
transition table:

State

Input symbol

0

q 1

q

q

q

1

1

3

q

q

q

q

0

1

2

3

1

q

q

q

q

0

2

3

3

Fig. 7.11