Nondeterministic FA: an FA that allows transitions on the empty string, , and states that have multiple transitions on the same character.

Derived from DFA class

To simulate NFA, I extended class DeterministicFiniteAutomaton to the new NFA class named NoneterministicFiniteAutomaton. The differences between DFA and NFA caused different structure for class. However, we need to transform the NFA to the DFA to emulate the real FA.

In NFA, transitions can be -transitions, which means one state can moved to different states when a same alphabet or nothing inputed. So I created those objects to prepare for describe a NFA which can be used for construct the equivalent DFA.

We can notice that there is a new type ETransitionSet. I think the type StateSet can not describe the -transitions well and we don't need to tell the computer which alphabet is inputed, so I defined it in the following way.

We can easily iterate over the -trasitions started from some one state and stably support the construction for DFA. And the construction function for this class has been defind in the following way.

Silly::FiniteAutomaton::StateSet Silly::NondeterministicFiniteAutomaton::delta(StateSet inputStates, Alphabet inputAlphabet) { StateSet target; for (auto it = inputStates.begin(); it != inputStates.end(); ++it) { auto dt = delta(*it, inputAlphabet); target.insert(dt.begin(), dt.end()); } return target; }

eClosure function will return a closures of states reachable by -transitions from states in the inputed state set. And delta function will returns .

NFA to DFA

Transforming NFA to DFA needs the method called the subset construction, which constructs new states by map state sets to states and it is realized by the construct function.

void Silly::NondeterministicFiniteAutomaton::construct() { if (constructed) { if (!states.empty() && !alphabets.empty()) return; } StateSet q0 = eClosure(StartState); std::set<StateSet> Q = {q0}; std::queue<StateSet> working; working.push(q0); std::map<std::pair<StateSet, Alphabet>, StateSet> T; while (!working.empty()) { StateSet q = dynamic_cast<StateSet &&>(working.front()); working.pop(); for (auto it = nAlphabets.begin(); it != nAlphabets.end(); ++it) { auto t = eClosure(delta(q, *it)); T[std::pair<StateSet, Alphabet>(q, *it)] = t; if (Q.find(t) == Q.end()) { Q.insert(t); working.push(t); } } } std::map<StateSet, State> stateMap; State st = 0; for (auto it = Q.begin(); it != Q.end(); ++it) { states.insert(st); stateMap[*it] = st++; } for (auto it = T.begin(); it != T.end(); ++it) { transitions[Move(stateMap[it->first.first], it->first.second)] = stateMap[it->second]; } for (auto it = Q.begin(); it != Q.end(); ++it) { bool isAccepting = false; for (auto si = it->begin(); si != it->end(); ++si) { if (nAcceptingStates.find(*si) != nAcceptingStates.end()) isAccepting = true; } if (isAccepting) { acceptingStates.insert(stateMap[*it]); } } alphabets = nAlphabets; constructed = true; }

As you see, by including the state set in the -closure of results from fiding all states moved from the previous state set recursively, we can construct a new DFA which equals with the NFA. That means we should search through all of -path of -transitions to get the whole graph to finish the task and we seems to use a depth-first search to get every states constructed. Finally we mapped each states and transformed the state set and the alphabet set into the base DFA class.

When the base DFA class has been constructed, the DFA can be available to match strings.

Test

The test cases seem like those we used to test DFA, but I manually set some parameters, such like nETransitions to describe all -transitions.