NFA simulation C++ implementation

Here, I provide C++ implementation of a Non-Deterministic Finite Automaton. An NFA is a finite state machine where from each state and a given input symbol, the automaton may move to several possible next states.

NFA accept the same set of languages as DFA, namely the regular languages, i.e., non-determinism does not add any more power to the machine and it is possible to convert an NFA to an equivalent DFA. There is time-space tradeoff between an NFA execution and its equivalent DFA execution. The DFA can be executed in time linear in the length of input string (see DFA simulation) but it can potentially have an exponential number of states than the underlying NFA. An NFA can be executed in time O(NM), where N is the number of states and M is the length of input string.

Thus, if the equivalent DFA of an NFA is small, it is advantageous to convert the NFA to DFA to save execution time. However, if the number of states in the NFA is small or the number of states in the equivalent DFA is large, it might be advantageous to execute the NFA directly.

Take a look at the C++ implementation.

One thought on “NFA simulation C++ implementation

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s