Question

Show that there is no finite-state automaton that recognizesthe set of bit strings containing an equal number of 0s and 1s.

Short answer

By the pigeonhole principle shows that there is no finite state automaton.

Step-by-step solution

Definition

Pigeonhole principle-if k is a positive integer and \(\left( {k + 1} \right)\) or more objects are placed into k boxes, then there is at least one box containing two or more objects.

Show that there is no finite state automaton that recognizes the set of bit strings containing an equal number of 0s and 1s.

The result can be show by a contradiction.

Let’s assume that the finite state automaton M accepts the set of bit strings that contains an equal number of 0’s and 1’s.

Let’s assume that M has n states and let’s consider the strings .Since the input contains more than inputs than states, there needs to exists some states that is visited at least twice for the input by the pigeonhole principle.

However,this then implies that M ends up in the same state with the input as the input.Since M accepts, M also needs to accept. This is a contradiction, as M accepts a string that does not contain an equal number of 0’s and 1’s.

Therefore, our assumption is wrong there does not exist a finite-state automaton.