Construct an NFA that accepts $L=\{x\#y \mid x,y\in\{0,1\}^k,x\not=y\}$

Question

Let $$k\geqslant 1, \quad \Sigma=\{0,1,\#\}$$ I am trying to construct an NFA that accepts the language $L$:

$$L=\{x\#y \mid x,y\in\{0,1\}^k,x\not=y\}$$

Now, here comes the tricky part: it should contain $O(k)$ states.

The best I could think of was $O(k^2)$ and of course that's not enough.

Can you think of something?

Answer 1

I claim that this is impossible: you can't do better than $\Theta(k^2)$.

To show this, let $\mathcal{A}$ be an NFA with state set $Q$ recognizing $L$. We're going to derive a lower bound on its number of states $|Q|$. Without loss of generality, let's suppose that all states of $\mathcal{A}$ are coaccessible; otherwise, we can remove the states of $\mathcal{A}$ that are not, and get a smaller NFA for $L$.

Let $Q_i$ be the set of states that can be reached after reading some word of length $i$. Suppose $q \in Q_i \cap Q_j$. Let $u,v$ be words that bring $\mathcal{A}$ into state $q$, with $|u|=i$ and $|v|=j$. Since $q$ is coaccessible, there is some $w$ that labels a path from $q$ to a final state; then both $uw$ and $vw$ are in $L$ so $|u|+|w| = |v|+|w| = 2k+1$ so $i = |u| = |v| = j$.

The contrapositive of what we just established is that for $i \neq j$, $Q_i$ and $Q_j$ are disjoint. Therefore,

$$|Q| \geq \left| \bigcup_{i=0}^k Q_i \right| \geq \sum_{i=0}^k |Q_i|$$

We now want lower bounds on the $|Q_i|$. Let $P_u$ be the set of states that can be reached after reading $u$. Thus $Q_i = \bigcup_{|u|=i} P_u$, so in particular $P_u \subseteq Q_{|u|}$. Observe that:

• if $P_u = P_v$ then $u^{-1}L = v^{-1}L$ where $u^{-1}L = \{ w \mid uw \in L \}$;
• if $u$ and $v$ are two distinct words of length $i \leq k$, then $u^{-1}L \neq v^{-1}L$ (since $0^{k-i}\#u0^{k-i}$ is in one but not the other);
• there are $2^i$ distinct words of length $i$ and $2^{|Q_i|}$ distinct subsets of $Q_i$.

Combining these facts we get for every $i \leq k$ that $2^i \leq 2^{|Q_i|}$ and therefore $|Q_i| \geq i$. Plugging this into our earlier inequality, we have

$$|Q| \geq \sum_{i=0}^k i = \frac{k(k+1)}{2} \geq \frac{k^2}{2}$$