Binary Comparison using automata

Question

The question is:

Construct a DFA, which accepts the following language, $\{\omega | \omega = a_1b_1a_2b_2...a_nb_n\}$ for some n, where $b_i, b_i\in \{0, 1\}$ and $a_1a_2...a_n > b_1b_2...b_n$

I was stuck at finding how many states should this DFA have. I think this DFA should have 4 state:

1. initial state(unknown which binary of $a_1a_2...a_n ,\ b_1b_2...b_n$ is bigger)
2. larger ($a_1a_2...a_n > b_1b_2...b_n$)
3. equal ($a_1a_2...a_n = b_1b_2...b_n$)
4. smaller($a_1a_2...a_n < b_1b_2...b_n$)

But the answer to this question implicitly shows 6 states, could anyone help analyse this problem?

Answer 1

Your states can’t be made to work. When you’re in the initial state and read $a_1$, you’ve no way to know whether $a_1\ldots a_n>b_1\ldots b_n$, $a_1\ldots a_n=b_1\ldots b_n$, or $a_1\ldots a_n<b_1\ldots b_n$, so you’ve no way to know what the appropriate transition is.

If $a_1\ldots a_n\ne b_1\ldots b_n$, there is a smallest $k\in\{1,\ldots,n\}$ such that $a_k\ne b_k$, and it’s not hard to see that $a_1\ldots a_n>b_1\ldots b_n$ if and only if $a_k>b_k$. Using that idea, I can construct a suitable DFA with five states; $q_0$ is the initial state, $q_4$ is the only acceptor state, and the transitions are as follows:

$$\begin{array}{} q_0\overset{0}\longrightarrow q_1&&q_0\overset{1}\longrightarrow q_2\\ q_1\overset{0}\longrightarrow q_0&&q_1\overset{1}\longrightarrow q_3\\ q_2\overset{0}\longrightarrow q_4&&q_2\overset{1}\longrightarrow q_0\\ q_3\overset{0}\longrightarrow q_3&&q_3\overset{1}\longrightarrow q_3\\ q_4\overset{0}\longrightarrow q_4&&q_4\overset{1}\longrightarrow q_4 \end{array}$$

After reading $a_1b_1\ldots a_kb_k$ for any $k$, the automaton will be in state $q_0$ if $a_1\ldots a_k=b_1\ldots b_k$. If $k$ is minimal such that $a_k\ne b_k$, then either $a_kb_k=10$ or $a_kb_k=01$. In the first case the automaton is in state $q_4$; in the second it’s in state $q_3$. Both are trap states, so in the first case the input is accepted, and in the second it is not.

I constructed this DFA on the assumption that the length of the input string would be even; if it was supposed to test for strings of odd length and reject them, some modification would be required.