Modeling DFA and NFA using HashMap Implementation

Question

I have to implement the following operations over automata in Java:

• Concatenation
• Kleene Star
• Union
• Intersection

Those operations are easier if the automaton is an NFA. I liked the implementation given in the following link Modelling a Finite Deterministic Automaton via this data but I think this does not fit well when modeling NFA, because of the key uniqueness restriction. Would you recommend me any workaround to modeling NFAs?

Answer 1

As someone who actually implemented these operations once (when building a scanner generator), I recommend building up the automaton as an NFA, then using an algorithm like the subset construction or Thompson's algorithm to convert it down to a DFA. This keeps the logic for combining automata together simple and elegant without sacrificing the speed of the resulting matching automaton.

Hope this helps!

Answer 2

I would recommend using DFA's. Though forming the NFA maybe easier on paper, checking a valid string against an NFA will be more complicated than verifying one against a DFA due to accounting for epsilon-jumps.

As far as modeling them, you should be able to write your own with only a few classes. Just think of what a DFA/NFA consists of:
- Start state
- Set of states (some of which are "acceptance" states)
- Set of transitions