Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10

This exercise is a bit more difficult than the previous one.

To solve this exercise, let’s use the following strategy: define states in which the automaton can be if it just reads a 1 or a 0.

– We can have a state S1 which means the automaton read 0s. Therefore, from the state S0 with a 0, the automaton goes to state S1. And in the state S1, if we read a 0, the machine stays in the same state. Because it is the state that tells us that we just read a 0.

– Another state S2, means we just read a 1. So, at S1, reading a 1, the machine transition to the state S2. Form S0, reading a 1, we also move to state S2. Because S2 is the state that means we just read a 1.

– Lastly, we need an extra state S3. It will be a final state. And we can only get to that state if we are at S2 (where we just read a 1) and we read a 0 (the strings ending with 10).

– After that, we check that every state does something when reading a 1 or a 0.

Find the state diagram below.

Deterministic finite-state automaton that recognizes the set of all bit strings that end with 10
Deterministic finite-state automaton that recognizes the set of all bit strings that end with 10

Notice that, at the state S3, reading a 0 should take the automata to the state S1. Because S1 is the state where you just read a 0. And, from S3 with a 1, the new state will be S2, because S2 is the state where we just read a 1.

We can also specify the transition function using the table below. Don’t forget to specify that S3 is the final state if use a state table.

 f 
States10
S0S2S1
S1S2S1
S2S3S2
S3S1S2
State table that specify the transition function of a deterministic finite-state
automaton that recognizes the set of all bit strings that end with 10.

Similar exercises: