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

To solve this exercise, we have to options.

We can answer using a state table or state diagram.

First, we need to consider that to be in the final state, we need first to start from S₀, and recognize a 0, and then a 1. This tells us that we should have at least three states. S₀ is the initial state, S₁ is the state where we already recognized a 0, and S₂ is a state where we first recognized a 0 and then a 1. Therefore, S₂ will be a final state.

Let’s see how the final automata will looks like.

	f
State	1	0
S0	S1
S1		S2
S2	S2	S2

Notice that in both cases, strings starting with 01 are recognized.

We have the initial state S₀ and a normal state S₁. The only way to be in the state S₂ is if the first input bit was 0 and the second one was 1.

After that, no matter what comes next, we stay in the final state S₂. Therefore, the automaton recognizes any bit string that starts with 01.

You can use any of the two representations. Just remember if you are using a state table, to specify what is (are) the final state (s).

Similar exercises:

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