# Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter

I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not find a solution for a proper NFA after multiple tries.

The solution of my DFA for the language provided above:

My attempts for the NFA are down below. I apologize for my messy handwriting but these were just rough works that I was drawing out on the go.

My first attempt at solving the NFA

My second attempt at solving the NFA

My third attempt at solving the NFA

• All DFAs are NFAs. If you have a DFA you are already done. Apr 6 '21 at 12:16
• Keep in mind that a DFA can be seen as a NFA. Also, could you be more precise about the definition of NFA you are using? Do you allow $\varepsilon$-transitions? Do you allow multiple initial states? The easiest way to construct a NFA would be a NFA with 3 initial states (one for each word you want to recognize). Apr 6 '21 at 12:17
• I know all DFAs are NFAs. I have been asked to make a separate NFA for the above problem. The NFA here does not allow empty string transitions. The accepted language is only baa, ab, or abb and no other string longer or shorter. Apr 6 '21 at 12:38
• @TashfeenChoudhury, then just add an additional transition that that leads to a new "dead" state. In this way you get a new NFA that is not a DFA. Apr 6 '21 at 20:01

The question is not clear as formed: if you want an NFA which is not a DFA and matches the language then you could take your DFA and add a new unreachable state with an $$\epsilon$$-transition to itself, or add other $$\epsilon$$-transition self-loops or many other things that will not change the language.
If the aim is to use non-determinism to reduce the size of the automaton, then you can omit the garbage state (so that the word would just "fall out of" the NFA at that point). Given that you have already optimised the paths for $$ab,abb$$ (based on their shared prefix) and $$baa$$ has no shared prefix or suffix with the other words, it looks like this is the only possible optimisation to be made.