Question

Show that there is no finite-state automaton with three states that recognizes the set of bit strings containing an even number of 1s and an even number of 0s.

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.

Proof that there is no finite-state automaton exists.

Let us consider three states\({s_0},{s_{1,}}{s_2}\).

Let start with the state be \({s_0}\).Since the empty string contain an even number of 1’s and even numbers of 0’s, so \({s_0}\). Be a final state.

Since the string 0 does not contain an even number of 0’s and string 1 does not contain an even number of 1’s, there must be transitions from \({s_0}\).to some other state for each input.

Moreover, both transitions from \({s_0}\).with the two inputs cannot lead to the same state as 0 transitions from s’ would lead to an accepting state, but the string 10 would then be accepted while 10 does not contain an even number of its nor an even number of 0’s.

Let the input 0 leads to a transition from \({s_0}\) to \({s_1}\)and let the input 1 leads to a transition from\({s_0}\)to \({s_2}\). Since the strings 0 and 1 are not in the generated set of bit strings \({s_1}\)and \({s_2}\) are not final state.

Since 00 and 11 need to be accepted, there is a transition with input 0 from the non -final state \({s_1}\)to the final state \({s_0}\)and there is a transition with input 1 from the non-final state \({s_2}\)to the final state \({s_0}\).

Check the final result.

If there is a transition from when the input is 1, then the string 011 would be accepted. Since 011 should not be accepted this then means that there is no transition from when the input is 1 and thus there should be a transition from when the input is 1.

If there is a transition from when the input is 1,then the string 000 would be accepted. However ,000 does not contain an even number of 0’s .Thus we have then derived a contradiction as 000 is in the generated language of the machine while it is not a string in the set of bit strings.

This then implies that our assumption is incorrect and thus such a machine does not exist.

Therefore, there is no finite-state automaton exist.