I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I can see that on the $q_0 $ state when we have an $a$ it should stay in the $q_0$ state and for the $q$ state when we have an $a$ it should go to the $q_0$ state but still dont understand the other information given well enough to construct the diagram.

If anyone could help me understand the problem below it would be much appreciated.

  • 1
    $\begingroup$ What have you tried and where did you get stuck? 4 and 5 are mechanic tasks, no insight necessary. 6. is badly put; "L(M')" is a correct answer, but probably not the one intended. I guess the instructor wants "set constructor syntax". $\endgroup$
    – Raphael
    Dec 7, 2015 at 13:06
  • 2
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Dec 7, 2015 at 13:07
  • $\begingroup$ I still cant really understand how to create a transition state diagram from the information given since all the resources ive found seem to approach these questions in a different way. Once I get the diagram I can probably do 5 and 6 but am still not able to understand enough of the question to make a diagram. As far as using images i didnt know there was an issue, ill try not to in the future. $\endgroup$
    – dmnte
    Dec 7, 2015 at 13:17
  • $\begingroup$ Are you given a fixed DFA $M$ on which to perform these tasks, or are you supposed to figure out what the effect is for arbitrary $M$? $\endgroup$ Dec 7, 2015 at 13:34
  • $\begingroup$ Note that $M'$ behaves almost exactly like $M$, except that after any prefix which $M$ would accept, $M'$ is allowed to start over instead. What kind of words could you accept in this way? $\endgroup$ Dec 7, 2015 at 13:39

1 Answer 1


Starting from the $M$ you gave in a comment (which you should really include in the question), we have the transition table $$\begin{array}{r|cc} \delta & 0 & 1 \\ \hline q_0 & q_1 & q_2\\ q_1 & q_0 & q_2\\ q_2 & q_2 & q_2 \end{array}$$ with $q_0$ the start state and $q_1$ the final state. Now we modify this to a new NFA $M'$ by adding another final state $q'_0$ and construct the transitions $\delta'$:

  • $\delta'(q'_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
  • $\delta'(q'_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
  • $\delta'(q_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
  • $\delta'(q_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
  • $\delta'(q_1, 0) = \{\delta(q_1, 0)\}=\{q_0\}$, since $\delta(q_1,0)=q_0\notin F$
  • $\delta'(q_1, 1) = \{\delta(q_1, 1)\}=\{q_2\}$, since $\delta(q_1,0)=q_2\notin F$
  • $\delta'(q_2, 0) = \{\delta(q_2, 0)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$
  • $\delta'(q_2, 1) = \{\delta(q_2, 1)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$

giving us this transition table for $M'$ $$\begin{array}{l|cc} \delta' & 0 & 1 \\ \hline \{q'_0\} & \{q_0,q_1\} & \{q_2\}\\ \{q_0\} & \{q_0,q_1\} & \{q_2\}\\ \{q_1\} & \{q_0\} & \{q_2\}\\ \{q_2\} & \{q_2\} & \{q_2\}\\ \{q_0,q_1\} & \{q_0,q_1\} & \{q_2\} \end{array}$$ with $\{q'_0\}$ the start state and $\{q'_0\}, \{q_1\}, \{q_0,q_1\}$ the final states. Notice that $\{q_0\}$ and $\{q_1\}$ are unreachable so can be eliminated from the NFA. Notice also that in both FAs, state $q_2$ is a "trap" state: once you enter it (on input $1$), you'll never leave. This means that neither FA will accept any string containing a $1$ and from there it's not too hard to see what $L(M)$ and $L(M')$ are.

  • $\begingroup$ Thanks for your answer it has helped me to understand whats going on more, but i still have something I dont understand. Based on what you have written I interpret the transition statements as If the original $(q_0,a)$ transitions to a final state add $q_0$ as a transition since it is an element of $F$ otherwise keep the original transition from $M$. When going through the question this approach works for me for all states except $q_1$ where they seem to be reversed. i.e on $q_1,1$ it transitions to $q_0$ originally but you have it going to $q_2$ why is this ? $\endgroup$
    – dmnte
    Dec 8, 2015 at 5:49
  • $\begingroup$ @dmnte. The table you gave in the comments has $\delta(q_1,1)=q_2$. $\endgroup$ Dec 8, 2015 at 15:17
  • $\begingroup$ oh yeah I wrote it wrong it should en up looking like this $$\begin{array}{l|cc} \delta & 0 & 1 \\ \hline q_0' & q_1,q_0 & q_2\\ q_0 & q_1,q_0 & q_2\\ q_1 & q_0 & q_2\\ q_2 & q_2 & q_2 \end{array}$$ So based on this diagram the strings of length 3 that are accepted are 000 and 010. As far as the accepted language, im not sure how to write it, obviously any number of 0's are accepted and if there is a 1 then more 0's need to follow but im having trouble writing it. Would this be right ? $(0^n + 1 + 0^m)^t | t,n,m \geq 1$ $\endgroup$
    – dmnte
    Dec 9, 2015 at 11:59
  • $\begingroup$ @dmnte. Not quite. Remember, that $q_2$ is a non-final trap state, so as I mentioned above, if you ever encounter a 1 in the input, the FA won't accept that word. The only words accepted by either FA will be strings of zeros. See which are accepted by $M$ and $M'$. BTW: I slightly edited the table for $M'$. $\endgroup$ Dec 9, 2015 at 15:52
  • $\begingroup$ there might be a bit of confusion based on my original table which was written wrong. it should have been: $$\begin{array}{r|cc} \delta & 0 & 1 \\ \hline q_0 & q_1 & q_2\\ q_1 & q_2 & q_0\\ q_2 & q_2 & q_2 \end{array}$$ and for $M'$ the above transition table is correct, so based on these, for $M$ the accepted language should be something like $0^{n+1}1^n | n,m\geq 0$. For $M'$ it would be something like what I wrote above were there can beany number of 0's but if there is a 1 it will go back to $q_0$ allowing for any number of 0's again. $0^n(10)^*| n\geq1$ seems close $\endgroup$
    – dmnte
    Dec 10, 2015 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.