<p>In dx.doi.org/10.1006/inco.2001.3069 the authors defined <span class="math-container">$NID_m = \{ u\in \{0,1\}^* | \exists i : u_i \neq u_{i + m} \}$</span> and claimed it could be recognized by a NFA of size <span class="math-container">$O(m)$</span>.  The paper mentions the NFA simply needs to guess a residue <span class="math-container">$i$</span> modulo <span class="math-container">$m$</span> and check whether there is a position <span class="math-container">$p \equiv i\,mod\,m$</span> with <span class="math-container">$u_p \neq u_{p + m}$</span>.  I suspect I'm overlooking something simple.  Can anyone point out how this can be done with a linear number of states?</p>

CC BY-SA 4.0
2022-06-01T22:20:22.013Z
Maybe better suited for cs.SE as you indeed overlook something simple. Initial state $q_i$ loops with $0,1$. And you have two states connected to state $q_i$, $q_0$ with a $0$ transition, and $q_1$  with a $1$ transition, that is when you "guess" $i$ (you exit state $q_i$). $q_0$ is followed by $m-1$ states connected by a path, all transitions being labeled by $0$ and $1$ but the last, labeled by $0$ only, that is, $u_{i+m}$ has to be $0$ ; last state is accepting and loops until the end of the word. Same trick with $q_1$ but the last transition is labeled by $1$.
holf
CC BY-SA 4.0
2022-06-02T02:10:18.857Z
Thank you for your comment.  I understand the claim properly now.
Alex Williams
<regular-language><nondeterminism>
Capturing a particular regular language with $O(m)$ states
Alex Williams
# Capturing a particular regular language with $O(m)$ states

(Asked by: username_0 on 2022-06-01)

In dx.doi.org/10.1006/inco.2001.3069 the authors defined $NID\_m = \{ u\in \{0,1\}^\* | \exists i : u\_i \neq u\_{i + m} \}$ and claimed it could be recognized by a NFA of size $O(m)$. The paper mentions the NFA simply needs to guess a residue $i$ modulo $m$ and check whether there is a position $p \equiv i\,mod\,m$ with $u\_p \neq u\_{p + m}$. I suspect I'm overlooking something simple. Can anyone point out how this can be done with a linear number of states?

**Tags:** regular-language, nondeterminism

> **Comments:**
> **username_1**: Maybe better suited for cs.SE as you indeed overlook something simple. Initial state $q_i$ loops with $0,1$. And you have two states connected to state $q_i$, $q_0$ with a $0$ transition, and $q_1$  with a $1$ transition, that is when you "guess" $i$ (you exit state $q_i$). $q_0$ is followed by $m-1$ states connected by a path, all transitions being labeled by $0$ and $1$ but the last, labeled by $0$ only, that is, $u_{i+m}$ has to be $0$ ; last state is accepting and loops until the end of the word. Same trick with $q_1$ but the last transition is labeled by $1$.  
> **username_0**: Thank you for your comment.  I understand the claim properly now.  

---

## 0 answers

