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.
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.
There's only three words, so just make three parallel paths for your NFA, using a transition function like the following:
Input State | Input Symbol | Output States |
---|---|---|
[start] | a | [a.b], [a.bb] |
[start] | b | [b.aa] |
[a.b] | b | [ab#] |
[a.bb] | b | [ab.b] |
[ab.b] | b | [abb#] |
[b.aa] | a | [ba.a] |
[ba.a] | a | [baa#] |
Here, state names are in brackets ([..]) and state names that end with "#" are terminal.
Generally it's considered easier to make an NFA than a DFA, so the usual method is to first make an NFA and then make the DFA by modifying the NFA by changing multiple output states to a single intermediate state.
If you followed this method for the above NFA, then the resulting DFA would look something like this (I have appended an "*" to the intermediate state names):
Input State | Input Symbol | Output State |
---|---|---|
[start] | a | [a.b*] |
[start] | b | [b.aa] |
[a.b*] | b | [ab.*] |
[ab.*] | (e) | [ab#] |
[ab.*] | b | [abb.*] |
[abb.*] | (e) | [abb#] |
[b.aa] | a | [ba.a] |
[ba.a] | a | [baa#] |
I've been a bit loose about all of the empty symbol/end-of-input transitons to terminal states. If you need me to fill al of them in, them I can do that.