Question

Show that there is no finite-state automaton with two states that recognizes the set of all bit strings that have one or more 1 bits and end with a 0.

Short answer

There is no finite-state automaton exist.

Step-by-step solution

Definition of finite-state automaton.

It is an abstract machine that can be exactly one of a finite number of state at any given time.

show that there is no finite-state automaton exists.

The result can be proved by a contradiction.

Suppose that such a machine exists, with starts \({s_{o,}}\) and other state\({s_{1,}}\). Because the empty string is not in the language but some strings are accepted, I must have \({{\bf{s}}_{{\bf{1,}}}}\)as the only final state, with at least one transition from to .Because the string 0 is not in the language, any transition from \({s_{o,}}\)to \({s_{1,}}\) so on input 0 must be to itself, so there must be a transition from\({s_{o,}}\)to \({s_{1,}}\) on input 1. But this cannot happen,because the string 1 is not in the language. This is a contradiction.

Therefore, there are no such finite- state automaton exists.