简单的NFA实现

Type	Reference
Source	SLScanner/NondeterministicFiniteAutomaton.cpp
Header	SLScanner/NondeterministicFiniteAutomaton.hpp
Test	SLScanner/TestNondeterministicFiniteAutomaton.cpp

Difference to DFA

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.

StateSet nStates;
AlphabetSet nAlphabets;
TransitionSet nTransitions;
ETransitionSet nETransitions;
StateSet nAcceptingStates;

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.

typedef std::multimap<State, State> ETransitionSet;
typedef std::pair<State, State> ETransition;

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.

NondeterministicFiniteAutomaton(
  StateSet states_,
  TransitionSet transitions_,
  ETransitionSet etransitions_,
  AlphabetSet alphabets,
  StateSet acceptingStates);

Necessary Functions

There are two function to construct the new available DFA named eClosure and delta.

StateSet eClosure(State input);
StateSet eClosure(StateSet inputs);
StateSet delta(State inputState, Alphabet inputAlphabet);
StateSet delta(StateSet inputStates, Alphabet inputAlphabet);

Silly::NondeterministicFiniteAutomaton::StateSet Silly::NondeterministicFiniteAutomaton::eClosure(State input) {
  std::queue<State> working;
  StateSet closure;
  closure.insert(input);
  working.push(input);
  while (!working.empty()) {
    State state = working.front();
    working.pop();
    for (auto it = nETransitions.find(state); it != nETransitions.end(); ++it) {
      if (it->first == state) {
        closure.insert(it->second);
        bool isNewState = false;
        for (auto fn = nETransitions.find(it->second); fn != nETransitions.end(); ++fn) {
          if (fn->first == it->second && closure.find(fn->second) == closure.end()) {
            isNewState = true;
            break;
          }
        }
        if (isNewState)
          working.push(it->second);
      }
    }
  }
  return closure;
}

Silly::NondeterministicFiniteAutomaton::StateSet Silly::NondeterministicFiniteAutomaton::eClosure(StateSet inputs) {
  StateSet closure;
  for (auto it = inputs.begin(); it != inputs.end(); ++it) {
    StateSet output = eClosure(*it);
    closure.insert(output.begin(), output.end());
  }
  return closure;
}


Silly::FiniteAutomaton::StateSet Silly::NondeterministicFiniteAutomaton::delta(State inputState, Alphabet inputAlphabet) {
  StateSet target;
  if (nTransitions.find(Move(inputState, inputAlphabet)) != nTransitions.end())
    target.insert(nTransitions[Move(inputState, inputAlphabet)]);
  return target;
}

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.

And the test result are omitted, you can try to test it by building the module TESTScanner, see SLScanner/TestNondeterministicFiniteAutomaton.cpp.