patternMinor
Minimal number of states for an NFA of all different words
Viewed 0 times
numbernfaallstateswordsdifferentforminimal
Problem
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:
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.
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.
Solution
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:
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.
Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:
- There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
- 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.
Context
StackExchange Computer Science Q#138797, answer score: 6
Revisions (0)
No revisions yet.