1
$\begingroup$

Task

Convert the following NFA to a DFA.

NFA to be solved.

My process

  1. 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.
  2. 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).
  3. Now it's time to solve L(M'') = L(M').
  4. 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).
  5. 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

The answer.

Questions

  1. 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"?
  2. 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"?
$\endgroup$
  • $\begingroup$ Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states $.^{[1]}$ The transitions without consuming an input symbol are called ε-transitions. ε-transitions provide a convenient way of modeling the systems whose current states are not precisely known. [1]How does an NFA use epsilon transitions? $\endgroup$ – W.R.P.S Sep 20 '18 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.