0
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ All DFAs are NFAs. If you have a DFA you are already done. $\endgroup$
    – Steven
    Apr 6 '21 at 12:16
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Apr 6 '21 at 12:17
  • $\begingroup$ 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. $\endgroup$ Apr 6 '21 at 12:38
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Apr 6 '21 at 20:01
0
$\begingroup$

For any language of finite cardinality you can make an NFA that has a totally separate linear path from the start node for each string in the language, with the last node of each path being an accepting node. In some sense this is the "simplest" NFA that accepts the language, and it may be what whoever set this question had in mind.

But as others have said, it's a silly question because any answer to the DFA part is automatically an answer to the NFA part.

$\endgroup$
1
  • $\begingroup$ This was really helpful to understand. $\endgroup$ Apr 6 '21 at 22:08
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, the question I have been given is not as clear but this clears up some confusion, $\endgroup$ Apr 6 '21 at 14:12

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.