0
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – plop Oct 5 '20 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.