Which are the best ways to implement a DFA?

Question

I know that DFA can be implemented using if-else approach and graph approach, but is there any other way of implementing them? Actually I am creating a JavaCode Generator for regular expressions, so far I have done two possible approaches (if-else, and graph approach) but I want to provide more possible ways. I think maybe it can be implemented using a some data structures as Set or Map for transitions.

Answer 1

Here is another way of implementing Automata, using enum. Seems cool.

http://java.dzone.com/articles/automaton-implementation-java

So as a conclusion I have made, there are 4 ways of implementing FSA: enum, if-else, switch case, graph, hashMap

Answer 2

You can also implement the DFA using JavaCC or Antlr like parser libraries. These libraries help in parsing the language grammar and building AST.

If you can model your DFA states as a set of acceptable grammar, you can use these libraries.

Answer 3

Implement a Node object. this is what you think it is. 'State' could be a better name. Implement an Input object. This abstracts the input (I don't know if you're implementing something for class or something super-industrial strength.)

The node could have Node transitionTo(Input input), boolean isAcceptState(), and boolean isErrorState() methods.

You'd initialize the node by creating a data structure of Inputs and the resulting Node outputs. It's really hard to say how this would work without knowing more.

Then the driver code is something like

while(!currentNode.isAcceptState() && !currentNode.isErrorState()) {
    currentNode  = currentNode.transitionTo(inputGetter.getInput());
    }

Without knowing what you're trying to accomplish it's harder to be more detailed.

Answer 4

I remember from school that there were four ways one was using a switch (pretty much like an if), and another using a map-like structure with keys as input and values as states.