Minimal number of states for an NFA of all different words

Question

Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.

Also, for me $k$ is a known constant. So the language ìs regular (at most $(2^k)\cdot (2^k-1)$ words).

I want to build the most efficient NFA for $L$. So far, I have been able to cone up with an NFA of $O(k^2)$ states, but I want to find one with $O(k)$ states. Of course one could argue that as $k$ is constant, its the same as $O(1)$, but assuming $k$ is a constant parameter - that is, given a value of $k$, I construct $L$ and an NFA for $L$ with $O(k)$ states.

My idea to use $k^2$ states:

• A path for each index, as $u$ and $v$ of size $k$... they differ means there is at least one $1\leq i \leq k$ where they differ at that character.
• Read '0' in $i$th character and '1' in $i+k+1$th character (due to '@'). Or other way.
• In between make sure that $u$s length and $v$s length is $k$. Which characters you read in between? I don't care.

But this will give me around $2k$ states (I can do a bit less, but still $O(k)$) for each index. Total $O(k^2)$, as there are $k$ indices.

I would ask for a way to improve my idea, to use $O(k)$ states. Or maybe a totally different approach.

Answer 1

Here is a matching $\Omega(k^2)$ lower bound.

Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:

1. There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
2. There is some word $z$ such that starting at $q$, after reading $z$ the NFA could be at an accepting state.

Since all words in $L$ have the same length, the sets $Q_i$ must be disjoint.

Now let $i \in \{0,\ldots,k\}$. For every word $w \in \{0,1\}^i$, let $Q_i(w) \subseteq Q_i$ be the set of states that the NFA could be in after reading $w$. I claim that if $w_1 \neq w_2$ then $Q_i(w_1) \neq Q_i(w_2)$. Indeed, the NFA behaves differently after reading $w_1$ and $w_2$: it accepts $w_1 0^{k-i} @ w_2 0^{k-i}$ but rejects $w_2 0^{k-i} @ w_2 0^{k-i}$. It follows that $2^{|Q_i|} \geq 2^i$, and so $|Q_i| \geq i$. Therefore the NFA has at least $$ \sum_{i=0}^k i = \Omega(k^2) $$ many states.

Answer 2

I don't understand how you could do this in less than $2^k$ states. Your description of your plan doesn't fit at all with how I understand NFAs. You talk about reading to the $i$th character, as if you had some kind of random access, but an NFA must read symbols in order, and any knowledge it needs from those symbols must be reflected as part of the state it transitions to afterwards.

Following is my argument that at least $2^k$ states are required.

Let $q_x$ be the state the machine reaches after reading $x \in \{0,1\}^k$, and let $u,v\in \{0,1\}^k\wedge u\neq v$. Is it possible that $q_u=q_v$? No, because there is at least one set of remaining symbols that $q_u$ must accept, and that $q_v$ must reject: namely, a repetition of $v$.

Therefore, $q_x$ must be unique for each $x$. Since $x$ is $k$ items long, there are $2^k$ unique $x$s, each needing their own distinct $q_x$.

This is a lower bound; in practice you will need at least $k$ more states to use while consuming $v$, and one for consuming the $@$ symbol.