Problem Detail: I’ve converted this NFA to a DFA and I get a similar soultion automata but I’m not sure if I really understand everything. Please correct me if I’m explaining it wrong, I would love some feedback. From the state 0 we only have the set {0} since there doesn’t exist any ε-transition. After that we have to input “a” to move to state 1 and here I’ve got a question. Does it include the 0 also since “a” can either take you to state 1 but also to state 0 since it loops? Continuing we want to move to state 2 via “a” input. Why does it include the “0”? Is it because you have to consider all the inputs from each set in the state 1? Like, if you input “a” at 0 you loop but you can also go to state 1. From 1 if you input “a” you move forward to state 2. Which gives us the set {0,1,2}. If this is correct, then the procedure for state 3 should be the same, right? Also, at the third state {0,1,2,3} he can’t just loop “b” since the other states can’t “handle” the input so you have to create a new state containing the set {0,3} which can handle the “b” input? Sorry if this is a bit long, I just want to understand what is going on really. 
Asked By : saturn
Answered By : T. Kiley
You’ve basically got it. The reason why the a loops is because whichever state you were in, you can end up in any one of them (if you were in 0, maybe you took the looping a and ended up in 0). The way I think of it is, with the NFA, you are maintaining a list of states you are in at any one point. When you convert to DFA, we have a state for any set of states we can be in (the power set of all the states in the NFA). We can tidy this up if we want (removing inaccessible nodes etc.) but that is the basic principle. So with yours, you state in state 0. Then we read an a and at this stage we could be in {0, 1}. Then we read in another a and now we could have done:
- Been in state 0 and stayed in state 0
- Been in state 0 and advanced to state 1
- Been in state 1 and advanced to state 2
Therefore we could now be in any of {0, 1, 2} so that’s the node we go to in the DFA.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18415
