0
$\begingroup$

I have been given the following NFA:

NFA

and, using the conversion algorithm (creating a new event for every union of events), I came up with the following DFA (note: I added here the events from the NFA, even if they are never accessed, for clarity on how the union events are formed):

NFA

However, I can clearly see that something is wrong: the NFA rejects the string "ababa", yet my DFA accepts it. The transition $\delta^*(\{A,C,D\},a)$ returns the event $\{A,B,D\}$, an accepting state. Through sheer intuition, I imagine it should instead return the event $\{A,B\}$, but I don't quite see what went wrong. I've redone this multiple times, each time with the same result. What I am doing wrong in my application of the theorem?

$\endgroup$
0
$\begingroup$

The NFA accepts the string "ababa":

A -> A -> A -> B -> C -> D

Remember that an NFA accepts if there is some path which leads to an accepting state.

$\endgroup$
1
  • $\begingroup$ wow, I can't believe I didn't see that. Good catch, thanks for the help. $\endgroup$
    – Devilius
    May 15 '17 at 3:18

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.