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!