Question: Converting NFA to DFA: Checking for Errors and Improving Technique

[Lolligirl]

Hello again everyone! I think I have at least a decent handle on this one, but I want to check my work.

Question: Convert the following NFA to an equivalent DFA (The D is going to B and the E to A on lambda).
https://dl.dropboxusercontent.com/u/5778771/Assignment4GivenNFA.jpg

Here is my DFA so far:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1.png

Are there any errors that pop out at any of you?

Thanks! :D

 

[I like Serena]

Hello again everyone! I think I have at least a decent handle on this one, but I want to check my work.

Question: Convert the following NFA to an equivalent DFA (The D is going to B and the E to A on lambda).Here is my DFA so far:Are there any errors that pop out at any of you?

Thanks! :D

Hi Lolligirl!

Well, your DFA will only accept words that the NFA also accepts, so that is good. :)
Oh, and you will need a start state.

However, the NFA allows loops back, but your DFA doesn't.
So the NFA would accept for instance [m]aaaa[/m], but your DFA doesn't.

 

[Lolligirl]

That...is a good point. Could I perhaps do this?

https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v2.png

...But, looking at it, now there's an extra character at the end before it wraps back around to 0. I could perhaps delete my state 4 altogether and simply make state 3 wrap around on an 'a' to state 0 which would then be an accept state...but then the DFA would accept strings the NFA doesn't. Could you give me a push in the right direction of where my mistake in logic is?

 

[Evgeny.Makarov]

I suggest using the procedure in the constructive proof that NFAs are reducible to DFAs. That's where the states of the new DFA are subsets of states of the NFA. In my attempt, the DFA ends up having only 5 states instead of the possible maximum of $2^5=32$.

 

[Lolligirl]

Okay, maybe you can help me clear something up here. My confusion starts at the bolded line (here I am relabeling the A, B, etc. letters for the original states as numbers to distinguish this DFA from the NFA on my paper; E(blah) is the epsilon closure of blah).

For convenience, here's the NFA again:
https://dl.dropboxusercontent.com/u/5778771/Assignment4GivenNFA.jpg

E(0) = {0} = A (renaming {0} to A)
E(move(A,a)) = E({1}) = {1} = B
E(move(A,b)) = E({Ø}) = {Ø} = Ø

E(B) aka E({1})
E(move(B,a)) = E({2,4}) = {0,2,4} = C
E(move(B,b)) = E({Ø}) = {Ø} = Ø

At this point, we have:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v3.jpg

Now, continuing:
E(C) aka E({0,2,4})
E(move(C,a)) = E({1})
OR
E(move(C,a)) = E({0,1,2,4})

^Which one of the two is it? Move(C,a) itself would be just {1} if I'm thinking of this correctly, but the epsilon closure of that is {1}...it feels like I'm leaving out the {0,2,4}. Hopefully you understand what I mean.

If I go along with E(move(C,a)) = E({1}), finish E(move(C,b)), as well as finish state D's outgoing arrows, this is the resulting DFA I get, but I'm not sure if it's correct:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v4.jpg

 

[Evgeny.Makarov]

here I am relabeling the A, B, etc. letters for the original states as numbers to distinguish this DFA from the NFA on my paper

I think it would be clearer to keep $A,B,\dots$ to be the state names of the old NFA and introduce new names like $P,Q,\dots$ or $1,2,\dots$ for the states of the new DFA.

Now, continuing:
E(C) aka E({0,2,4})
E(move(C,a)) = E({1})
OR
E(move(C,a)) = E({0,1,2,4})

^Which one of the two is it?

The first variant is correct. The transition function $\operatorname{move}'$ of the DFA is defined as
\[
\operatorname{move}'(R,a)=E\left(\bigcup_{r\in R}\operatorname{move}(r,a)\right).
\]
Here $r$ is one of the old states and $R$ is a subset of the old states. For this automaton, $\bigcup_{r\in\{0,2,4\}}\operatorname{move}(r,a)=\{1\}$ and $E(\{1\})=\{1\}=B$.

Move(C,a) itself would be just {1} if I'm thinking of this correctly, but the epsilon closure of that is {1}

That is correct. Your resulting DFA is also correct.

 

[Lolligirl]

...Oh! So that's what that notation means! I keep seeing that notation with unions and belongs to and primes everywhere, but I never really saw it used next to a picture, so I didn't understand what it was trying to say. Thank you so much for clearing that up, Evgeny; now I see how my thinking was right, and how to improve my technique further (as well as improve my notation)! :D