0
$\begingroup$

The question is the following

"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."

I was wondering if there is a rigourous proof method for showing results such as the previous one. My solution is the following:

Suppose such a FSA exists: then it has three states, $s_{0},s_{1},s_{2}$. Suppose $s_{0}$ is the starting state. Since the empty string is not in the language, there must be a transition towards $s_{1}$ or $s_{2}$ .

Suppose there is a transition $s_{0} \rightarrow s_{1}$ with label 1. Then $s_{1}$ can't be a final state, otherwise the string $1$ would be recognized. Therefore, the only final state can be considered $s_{2}$. Since the strign $10$ must be recognized, there must be a transition $s_{1} \rightarrow s_{2}$ with label 0. But the same automaton must recognize also the string $01$.

Now we can't introduce a transition $s_{0} \rightarrow s_{2}$ with label 0, since this would allow the FSA to recognize the stirng $0$. If we accept a transition $s_{0} \rightarrow s_{1}$ with label 0, then the string 00 would be recognized. So there are no further transitions we can define that allow the FSA to recognize both 10 and 01 and that preserve the original number of states.

Can this reasoning be considered correct? Thanks in advance

$\endgroup$
1
  • $\begingroup$ It’s simpler... just say that after the prefixes $0$, $1$, $01$ and $\varepsilon$, the automaton must be in four different states, because after these prefixes it must accept four different sets of suffixes. $\endgroup$
    – mjqxxxx
    Commented Nov 3, 2021 at 14:02

1 Answer 1

1
$\begingroup$

A reasoning along your lines would in principle work.

However, your reasoning is for the language where the numbers of $0$ and $1$ are odd, not even as in the problem setting. $01$ and $10$ do not have even numbers although they are of even length.

If you have this machinery available, you can use the syntactic congruence and the minimal automaton; no other automaton can have a lower number of states than this / have a lower number of states than the number of congruence classes. This number is four in this case.

Without these results, a reasoning along your lines is pretty much the best you can do. Maybe a slightly more systematic approach would be dividing all bitstrings into four classes:

  1. even number of $0$, even number of $1$
  2. odd number of $0$, even number of $1$
  3. even number of $0$, odd number of $1$
  4. odd number of $0$, odd number of $1$

This is a partition of the set of all bitstrings. For any string there are possible continuations that bring it into the language. But for no two strings from distinct classes these continuations are the same (add some detail here if necessary). Therefore reading them must bring the automaton to distinct states, which in turn means there must be at least four states.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .