What is the correct FSA representation of the following string sequence? Based on this article, i am trying to imagine how i would construct an FSA based index for the following string sequence:


ABCDEF
ABDDDF
ABDDEFGHI


These are the representations that i found:

There are problems with each:

The first introduces a new key in the automata that really isn't in the set (ABCDEFGHI)

The second one is the closest to my heart but it is more trie-like, so it can be inefficient at a large scale.

The third saves a lot of final states therefore saves some space. However, state 9 has multiple "F" transitions which i think is illegal.

So the big question is: Which one of the above is correct? If none of them, please share what is the correct!

Thank you
I think none of your finite automata accepts the third string ABDDEFGHI.The following is what I think a correct finite automaton for accepting all three strings



In case where your language has the third string ABDDDFGHI.The first is wrong since it accepts another string.The third also seems incorrect since there are multiple labels of same letter exiting from one node.Your second automaton is correct but you may want something like this