0
$\begingroup$

I have this NFA:

Image of NFA

I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when selecting a letter. However here the problem starts at {1}, where the dfa wouldn't have any connection for letter a and thus wouldn't be a proper DFA. How can I resolve this ?

$\endgroup$
0
1
$\begingroup$

You missed state $\emptyset$. The transition from state $1$ when character $a$ is read goes to $\emptyset$.

Since all transition from $\emptyset$ also go to $\emptyset$, you can also use the standard convention of omitting $\emptyset$ (and the transition for character $a$ from state $1$).

If a DFA has some missing transitions, it can always be completed by first adding a non-final state $q$, and then adding all missing transitions to $q$.

$\endgroup$
1
  • $\begingroup$ great thank you $\endgroup$ Nov 6 '21 at 16:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.