This exercise comes from Introduction to Automata Theory, Languages, and Computation, Second Edition, by Hopcroft, Motwani and Ullman.

Exercise Description

Give DFA's accepting the following languages over the alphabet .

1. The set of all strings ending in 00.
2. The set of all strings with three consecutive 0's (not necessarily at the end).
3. The set of strings with 011 as a substring.

Solution

1)

The finite automaton implementing this language is defined by:

where,

The transition function is defined by the following transition diagram:

2)

The finite automaton implementing this language is defined by:

where,

The transition function is defined by the following transition diagram:

3)

The finite automaton implementing this language is defined by:

where,

The transition function is defined by the following transition diagram: