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.

17.385044
78.486671

### Like this:

Like Loading...

*Related*

This question has been answered earlier here: https://kartikkukreja.wordpress.com/2013/04/18/nfa-to-dfa-conversion/comment-page-1/#comment-49