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?
