# What input does this NFA accept?

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?

• What about 01? Or 000000001? – G. Bach Nov 30 '15 at 1:49
• 00 or (01)+0 or empty string - e – Srinivas Reddy Thatiparthy Nov 30 '15 at 5:20
$(0+01)^*(\epsilon+00)0^*$
$(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.
• Your regular expression doesn't represent the string $01\ 00\ 01$ (spaces only for clarity). It should be $(0 + 01)^*$ or something equivalent. – Rick Decker Nov 30 '15 at 18:37