0
$\begingroup$

First sorry for the poor pictures, but I think they are ok enough to get the point across.

I would like to see the steps involved to convert this NFA to a DFA using the method explained in this youtube video.

enter image description here

I am specifically stuck on the part where he creates the second table. Here is a picture of my try at creating the first table.

enter image description here

And my try for the second table

enter preformatted text here

The resulting DFA from this though does not make sense. There is no way to get to state "q0q1", I assume my mistake lies in how I creates table 2. After working through this I see that I might have missed adding "q0" as a entry in table 2 (which would then allow me to get into state "q0q1").

Does that mean, when creating the second table, you always "grandfather" the start state in, and then all other states from the epsilon column in table 1? (then fill out the rest until all epsilon states are accounted for in table 2?).

Could someone show me the proper table 2? I can recreate the DFA from that, it is just creating table two that is confusing to me.

EDIT: I specifically ask the question because I do not understand how my teacher came to this solution (Sorry, teachers handwriting is worse than my pictures)

enter image description here

I just don't see how (in the DFA) you can leave state "q0" with a "0" input when the NFA does not have this transition.

$\endgroup$

1 Answer 1

0
$\begingroup$

This is because "$0$" in the DFA can represent a path "$\epsilon 0$" in the NFA.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .