We will follow a similar approach to previous exercises to solve this exercise.
Let’s define 4 states as follows:
- S0, the initial state
- S1 is the state when the automata read a 0
- S2 is the state when the automata read a sequence of two 0s
- S3 is the state when the automata read a sequence of three 0s. The automaton shouldn’t recognize a string with three consecutive 0s. Therefore, this cannot be a final state.
After the definition of the previous states, we can also define the following transitions:
- From the initial state with a 1, there is no need to change to a different state. This must be a final state, so the automaton will recognize strings that end in 1 without having more than 2 consecutive 0s.
- Reading a 0 at the initial state, the new state will be S1, this state is also final, so the automaton can recognize strings ending in one 0.
- At S1, reading a 0, the automaton will go to the next state S2 (reading two consecutive 0s). This is also a final state because the automaton should recognize strings with two consecutive 0s.
- At S2, reading a 1, the automaton will go to the final state S0.
- At S2, reading a 0, the automaton will go to the state S3. At this point, the string cannot be recognized because it has three consecutive 0s. So, if there are more 1s or 0s, the automaton will stay at the same state S3.
We can also specify the transition function using the table below. Don’t forget to specify that S0, S1, and S2 are final states if you use a state table.
| f | ||
| States | 1 | 0 |
| S0 | S0 | S1 |
| S1 | S0 | S2 |
| S2 | S0 | S3 |
| S3 | S3 | S3 |
Similar exercises:
- Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01
- Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10
- Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101
