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.