I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a little unsure. It would seem that as long as any 1 in the string has a 0 on either side of it (ex. 0100 or 01010), it would be acceptable. Am I missing something here?

enter image description here

  • 1
    $\begingroup$ What about 01? Or 000000001? $\endgroup$ – G. Bach Nov 30 '15 at 1:49
  • $\begingroup$ 00 or (01)+0 or empty string - e $\endgroup$ – Srinivas Reddy Thatiparthy Nov 30 '15 at 5:20
  • $\begingroup$ What is your specific confusion? What prevents you from answering the question on your own, or being confident in your answer? Have you tried to prove your answer correct? $\endgroup$ – D.W. Nov 30 '15 at 6:43

$(0^*(01)^*)^*(0^* + 000^*)$

You generally want to remove all the states one by one until you're left with only one or two states(when the start is not a final state). Say, you want to remove a state $l$; look at all the predecessors $p_i$ of $l$ and all the successors $s_i$ of $l$. Now any edge from a pred can come to $l$, may loop on $l$ or not and then go to any $s_i$.
Consequently, for each $p_i$ remove the edge $p_i \to l$ bearing the label (say) $A_i$, and for each edge $l \to s_i$ bearing the label say $B_i$, introduce a new edge $p_i \to s_i$ with the label $A_iL*B_i$ where $L$ is the label of the self-loop on $l$ (if any). For an already existing $p_i \to s_i$, add it to its label.

  • $\begingroup$ Your regular expression doesn't represent the string $01\ 00\ 01$ (spaces only for clarity). It should be $(0 + 01)^*$ or something equivalent. $\endgroup$ – Rick Decker Nov 30 '15 at 18:37
  • $\begingroup$ You're right. I corrected the answer. $\endgroup$ – DebD Dec 1 '15 at 11:50

Your Answer

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

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