Task
Convert the following NFA to a DFA.
My process
- Our goal is to achieve the following L(M'') = L(M') = L(M) where M is our NFA and L(M) is the set of all strings that M accepts.
- Make sure that I don't have any state transitions that accept more than 1 character. This step is not needed on this NFA cause there are none. We can assume L(M') = L(M).
- Now it's time to solve L(M'') = L(M').
- First we want to create a state that is our entering (initial) state. In other words, without reading any characters which states can we reach? We can reach (1, 2).
- From our initial state (1,2) we now want to try all possible transitions with our set of characters. In other words, with 'a' which state(s) will we arrive to. Same with 'b'. We keep iterating this process until all transitions are covered as well as marking out valid acceptors (exits).
Answer
Questions
- From (1, 2) we have a "loop" with the transition of 'a'. How come this is valid? From state 1 we do get back to 1 with 'a'. But with state 2 there is no transition including 'a'? Is this because 2 is connected to an "exit"?
- Similar to question 1, from state (2, 3) I do understand that 'b' would loop from both states but what about 'a'? I see that 'a' would "loop" from state 3. But 2 doesn't have any transition including 'a'? Is this the same as question 1 where it's because 2 is connected to an "exit"?