# NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $$\{0,1\}^{\ast}$$ that have two zeros separated by a string of length 4i, for some $$i \geq 1$$.

Let $$A = \{w \mid w \in \{0,1\}^{\ast}$$ have two zeros separated by a string of length $$4i$$, for $$i \geq 1\}$$. Then we design a NFA that recognizes A

Let $$M = (Q, \Sigma, \delta, q_{0}, F)$$ , where

$$Q = \{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}\}$$,

$$\Sigma = \{0, 1\}$$

for any $$q \in Q$$ and $$a \in \Sigma$$

$$\delta(q, a) = \begin{cases} \{q_{0}\} & q = q_{0},\ a = 1\\ \{q_{0}, q_{1}\} & q = q_{0},\ a = 0\\ \{q_{2}\} & q = q_{1},\ a = 0\ or\ a = 1\\ \{q_{3}\} & q = q_{2},\ a = 0\ or\ a = 1\\ \{q_{4}\} & q = q_{3},\ a = 0\ or\ a = 1\\ \{q_{5}\} & q = q_{4},\ a = 0\ or\ a = 1\\ \{q_{2}\} & q = q_{5},\ a = 1\\ \{q_{2}, q_{6}\} & q = q_{5},\ a = 0\\ \{q_{6}\} & q = q_{6},\ a = 0\ or\ a = 1\\ \end{cases}$$

$$q_{0}$$ is the start state, and

$$F = \{q_{6}\}$$

The state diagram is as follows:

I am not quite sure it is totally correct. Does $$q_{0}$$ should be a final state?

• If you make $q_0$ a final state then you could accept all of $\{0,1\}^*$. It look okay to me the way it is. – plop Oct 5 '20 at 21:43