Optimal way to represent a DFA?

[Fryguy8]

What is the optimal way to represent a Deterministic Finite Automaton? For those who don't know:

Set of states
an alphabet
Set of transition rules that map a state and an element from the alphabet to another state
a start state
a set of final states

Basically it's a structured digraph, with each state being a node, and each edge being a transition rule from one state pointing to another, labeled with an element from the alphabet.

For every state, every element of the alphabet must be mapped.

The automaton then accepts an input string and "parses" it using it's set of rules, and if it ends on a final state, it accepts, otherwise it rejects.

What is the optimal way to represent the 5 things that make up the DFA? The states should be a linked list in a sense. So the head of the list is the start state, and each node of the linked list contains a hash table mapping each element of the alphabet to another node on the list. Each node should also have a boolean property final. When the input has been parsed, check the property of the node you are on, and return true or false accordingly.

Note: I don't have to implement this, so worrying about whether the language supports lists like this isn't a concern.

[cybertron]

I'm actually working on porting a project using a DFA from Pascal to Java right now and that sounds like essentially the way we're doing it. We have a node object that stores all of the appropriate information and has a pointer to the next node(s). I won't guarantee that that is the best way to do it, but the guy who originally wrote the program worked on stuff like this for his PhD, so I would think he knows what he's doing :)

[Fryguy8]

i actually modified it a bit, so that there's a hash table of state objects. Each state object has it's name, whether it's final, and a map of transitions to other states, should work pretty well. Not sure how well the exactly implementation will work out, but we'll see :)

[bwkaz]

I'd have used a node object containing the finality/nonfinality flag, and a hashtable of other nodes (the hashtable would be keyed by the letter received). I'd have one fixed variable holding a reference (or pointer, depending on language) to the start node.

Maybe I could even build the set of nodes in an array, and then get rid of the array when I'm done building the interconnects from the list of transitions (without actually destroying the nodes)...

[Fryguy8]

bwkaz, that's very similar to the idea I ended up proposing.

thanks for the input guys :)

[cybertron]

I was trying to figure out why I don't have hash tables in any of my nodes, and then I realized that each of my nodes only has to remember at most two possible next states so there's really no point. It's not really important to this thread, but it makes me feel better:)