Question

Use Exercise 39 and finite-state automata constructed in Example 6 to find deterministic finite-state automata that recognize each of these sets.

a) The set of bit strings that do not begin with two 0s.

b) The set of bit strings that do not end with two 0s.

c) The set of bit strings that contain at most one 0 (that is, that do not contain at least two 0s).

Short answer

(a) The set of bit strings that do not begin with two 0s then M with the final state turned into non-final state and the non-final states turned into final state.

b) The set of bit strings that do not end with two 0s then M with the final state turned into non-final state and the non-final states turned into final state.

c) The set of bit strings that contain at most one 0 (that is, that do not contain at least two 0s) then M with the final state turned into non-final state and the non-final states turned into final state.

Step-by-step solution

Determine that the set of bit string do no begin with two 0’s.

In a fig, the deterministic state automaton M was given that recognizes bit strings that begin with two 0’s. The automaton has one final state\({s_2}\) , while the other three states \({s_0},{s_1},{s_3}\)are not final states.

Final state=\({s_2}\)

Non- final state=\({s_0},{s_1},{s_3}\)

The deterministic finite state automation that recognizes bit strings that do NOT being with two0’s is then M/ with the final state into non-final state and the non-final turned into final state.

Final state=\({s_0},{s_1},{s_3}\)

Non final state=\({s_2}\)

Therefore, the set of bit strings that do not begin with two s

Find that the set of bit strings that do not end with two 0s.

In a fig.,the deterministic state automaton M was given that recognizes bit strings that begin with two 0’s. The automaton has one final state\({s_2}\), while the other two states \({s_0}\)and \({s_1}\)a are not final states.

Final state=\({s_2}\)

Non- final state=\({s_0},{s_2}\)

The deterministic finte state automation that recognizes bit strings that do NOT being with two 0’s is then M/ with the final state into non-final state and the non-final turned into final state.

Final state=\({s_0},{s_2}\)

Non final state=\({s_2}\)

Therefore, the set of bit strings that do not end with two 0s.

Evaluate that the set of bit strings that contain at most one 0.

In a fig. the deterministic state automaton M was given that recognizes bit strings that begin with two 0’s. The automaton has one final state\({s_2}\) while the other two states \({s_0}\)and \({s_1}\)are not final states.

Final state=\({s_2}\)

Non- final state=\({s_0},{s_1}\)

The deterministic finite state automation that recognizes bit strings that do NOT being with two 0’s is then M/ with the final state into non-final state and the non-final turned into final state.

Final state=\({s_0},{s_1}\)

Non final state=\({s_2}\)

Therefore, the set of bit strings that contain at most one 0 (that is, that do not contain at least two 0s).