reg::nfa::builder Class Reference

Constructs NFAs step by step. More...

#include <nfa.h>

Classes
struct	pImpl
	Private implementation details of NFA builders. More...

Public Member Functions
	builder ()
	Constructs a blank builder object. More...
	builder (nfa const &nfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given NFA. More...
	builder (dfa const &dfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given DFA. More...
	builder (builder const &b)
	Copy-constructs a builder by copying another one's private implementation object. More...
	builder (builder &&b)
	Move-constructs a builder by stealing another one's private implementation object. More...
builder &	operator= (builder const &b)
	Copy-assigns a builder by copying another one's private implementation object. More...
builder &	operator= (builder &&b)
	Move-assigns a builder by stealing another one's private implementation object. More...
builder &	addSymbol (char32_t symbol)
	Adds a symbol to the prospective NFA's alphabet. More...
builder &	addSymbol (std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
builder &	setAccepting (std::string const &state, bool accept)
	Sets whether or not a state will be accepting within the prospective NFA. More...
builder &	makeInitial (std::string const &state)
	Resets the initial state for the prospective NFA. More...
builder &	addTransition (std::string const &from, std::string const &to, char32_t symbol)
	Adds a transition for the prospective NFA. More...
builder &	addTransition (std::string const &from, std::string const &to, std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
builder &	unite (nfa const &other)
	Makes the prospective NFA also accept every word of another NFA's language. More...
builder &	intersect (nfa const &other)
	Makes the prospective NFA accept only words accepted also by another NFA. More...
builder &	normalizeStateNames (std::string const &prefix)
	Reduces the prospective NFA's state names to consecutive numbers, prefixed with a given string. More...
nfa	build ()
	Builds the NFA, as defined by previous operations. More...

Detailed Description

Constructs NFAs step by step.

Any mention of a symbol or state will add them to the alphabet/set of states. The first state mentioned will be designated initial state.

Definition at line 62 of file nfa.h.

Constructor & Destructor Documentation

builder() [1/5]

reg::nfa::builder::builder

(

)

Constructs a blank builder object.

Definition at line 455 of file nfa.cpp.

: p(new pImpl) {}

builder() [2/5]

reg::nfa::builder::builder

(

nfa const &

nfa

)

Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given NFA.

Definition at line 458 of file nfa.cpp.

                                  : p(new pImpl) {
  makeInitial(nfa.getLabelOf(0));
  for (char32_t symbol : nfa.getAlphabet()) {
    addSymbol(symbol);
  }
  for (size_t qi = 0; qi < nfa.p->labels.size(); ++qi) {
    string const& qLabel = nfa.getLabelOf(qi);
    for (char32_t symbol : p->alphabet) {
      valarray<bool> ps = nfa.delta(qi, symbol);
      size_t pi(0);
      for (bool pb : ps) {
        if (pb) {
          addTransition(qLabel, nfa.getLabelOf(pi), symbol);
        }
        pi++;
      }
    }
    if (nfa.isAccepting(qi)) {
      setAccepting(qLabel, true);
    }
  }
}

builder() [3/5]

reg::nfa::builder::builder

(

dfa const &

dfa

)

Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a given DFA.

Transition destinations will be converted to singleton sets of the respective reached states.

Definition at line 483 of file nfa.cpp.

                                  {
  string initial(dfa.getLabelOf(0));
  unordered_set<string> acceptingStates;
  unordered_set<char32_t> alphabet(dfa.getAlphabet().begin(), dfa.getAlphabet().end());
  Ntransitionmap transitions;
  for (size_t q(0); q < dfa.getNumberOfStates(); q++) {
    for (char32_t symbol : alphabet) {
      transitions[dfa.getLabelOf(q)][symbol].insert(dfa.getLabelOf(dfa.delta(q, symbol)));
    }
    if (dfa.isAccepting(q)) {
      acceptingStates.insert(dfa.getLabelOf(q));
    }
  }
  p = make_unique<pImpl>(initial, acceptingStates, alphabet, transitions);
}

builder() [4/5]

reg::nfa::builder::builder

(

builder const &

b

)

Copy-constructs a builder by copying another one's private implementation object.

Definition at line 500 of file nfa.cpp.

: p(new pImpl(*(b.p))) {}

builder() [5/5]

reg::nfa::builder::builder

(

builder &&

b

)

Move-constructs a builder by stealing another one's private implementation object.

The other builder will be blank afterwards.

Definition at line 504 of file nfa.cpp.

: p(new pImpl) {p.swap(b.p);}

Member Function Documentation

addSymbol() [1/2]

nfa::builder & reg::nfa::builder::addSymbol

(

char32_t

symbol

)

Adds a symbol to the prospective NFA's alphabet.

Parameters

symbol

the symbol to add

Returns

reference to this object, for chaining operations

Definition at line 529 of file nfa.cpp.

                                                 {
  p->alphabet.insert(symbol);
  return *this;
}

addSymbol() [2/2]

nfa::builder & reg::nfa::builder::addSymbol

(

std::string const &

utf8Symbol

)

Same as above for a UTF-8-encoded symbol.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 535 of file nfa.cpp.

                                                          {
  return addSymbol(converter.from_bytes(utf8Symbol)[0]);
}

addTransition() [1/2]

nfa::builder & reg::nfa::builder::addTransition	(	std::string const &	from,
		std::string const &	to,
		char32_t	symbol
	)

Adds a transition for the prospective NFA.

Parameters

from	the starting state for the transition
to	the destination state for the transition
symbol	the symbol triggering the transition or \0 for an ε-transition

Returns

reference to this object, for chaining operations

Definition at line 576 of file nfa.cpp.

                                                                                           {
  if (p->transitions.empty()) {
    p->initial = from;
  }
  p->transitions[to];
  p->transitions[from][symbol].insert(to);
  addSymbol(symbol);
  return *this;
}

addTransition() [2/2]

nfa::builder & reg::nfa::builder::addTransition	(	std::string const &	from,
		std::string const &	to,
		std::string const &	utf8Symbol
	)

Same as above for a UTF-8-encoded symbol.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 587 of file nfa.cpp.

                                                                                                    {
  return addTransition(from, to, converter.from_bytes(utf8Symbol)[0]);
}

build()

nfa reg::nfa::builder::build

(

)

Builds the NFA, as defined by previous operations.

Returns

an NFA object with exactly the states, alphabet and transitions that were defined

Definition at line 771 of file nfa.cpp.

                      {
  p->alphabet.insert(U'\0');
  vector<char32_t> alphabetV(p->alphabet.begin(), p->alphabet.end());
  std::sort(alphabetV.begin(), alphabetV.end());
  vector<string> labelV(p->transitions.size());
  labelV[0] = p->initial;
  valarray<bool> acceptingV(p->transitions.size());
  acceptingV[0] = (p->acceptingStates.find(p->initial) != p->acceptingStates.end());
  size_t i(1);
  for (auto entry : p->transitions) {
    if (entry.first == p->initial) {
      continue;
    }
    labelV[i] = entry.first;
    acceptingV[i++] = (
      p->acceptingStates.find(entry.first) != p->acceptingStates.end()
    );
  }
  vector<vector<valarray<bool>>> transitionV(
    p->transitions.size(),
    vector<valarray<bool>>(
      p->alphabet.size()+1,
      valarray<bool>(labelV.size())
    )
  );
  unordered_set<string> emptySet;
  size_t qi(0);
  for (auto const& q : labelV) {
    unordered_map<char32_t,unordered_set<string>> const& fromQ = p->transitions[q];
    size_t si(0);
    for (char32_t symbol : alphabetV) {
      auto to = fromQ.find(symbol);
      unordered_set<string> const& viaSymbol(to != fromQ.end() ? to->second : emptySet);
      i = 0;
      for (auto const& p : labelV) {
        transitionV[qi][si][i++] = (viaSymbol.count(p) != 0);
      }
      si++;
    }
    qi++;
  }
  return {alphabetV, transitionV, labelV, acceptingV};
}

intersect()

nfa::builder & reg::nfa::builder::intersect

(

nfa const &

other

)

Makes the prospective NFA accept only words accepted also by another NFA.

Concatenates the names of states defined so far with the other NFA's state names and resolves conflicts by appending _.

Parameters

other

the NFA whose language should also be accepted

Returns

reference to this object, for chaining operations

Definition at line 694 of file nfa.cpp.

                                                  {
  if (!p->transitions.empty()) {
    vector<string> stateNames;
    stateNames.reserve(p->transitions.size());
    stateNames.push_back(p->initial);
    for (auto const& fromTo : p->transitions) {
      if (fromTo.first != p->initial) {
        stateNames.push_back(fromTo.first);
      }
    }
    auto const& oAlph = other.getAlphabet();
    size_t commonSymbols = 0;
    for (char32_t symbol : p->alphabet) {
      if (index_of(oAlph, symbol) < oAlph.size()) {
        commonSymbols++;
      } else {
        for (auto & fromVia : p->transitions) {
          fromVia.second.erase(symbol);
        }
      }
    }
    p->alphabet.insert(oAlph.begin(), oAlph.end());
    Ntransitionmap newTr(stateNames.size() * other.getNumberOfStates());
    unordered_set<string> newAcc(stateNames.size() * other.getNumberOfStates());
    unordered_map<size_t, unordered_map<size_t, string const*>> pairToName(stateNames.size() * other.getNumberOfStates());
    for (size_t q = 0; q < stateNames.size(); q++) {
      for (size_t qq = 0; qq < other.getNumberOfStates(); qq++) {
        string potentialName = stateNames[q] + other.getLabelOf(qq);
        for (auto nameIt = newTr.find(potentialName); nameIt != newTr.end(); nameIt = newTr.find(potentialName)) {
          potentialName.append("_");
        }
        auto nameIt = newTr.emplace(potentialName, commonSymbols);
        pairToName.emplace(q, 1).first->second.emplace(qq, &(nameIt.first->first));
        if (p->acceptingStates.find(stateNames[q]) != p->acceptingStates.end() && other.isAccepting(qq)) {
          newAcc.insert(potentialName);
        }
      }
      p->transitions[stateNames[q]][U'\0'].insert(stateNames[q]);
      // Needed due to the equivalence of standing still to “taking” an ε-transition.
    }
    for (size_t q = 0; q < stateNames.size(); q++) {
      auto const& qLabel = stateNames[q];
      auto const& viaTos = p->transitions[qLabel];
      for (auto const& viaTo : viaTos) {
        for (size_t qq = 0; qq < other.getNumberOfStates(); qq++) {
          valarray<bool> const& reached = other.delta(qq, viaTo.first);
          for (auto const& to : viaTo.second) {
            size_t p = index_of(stateNames, to);
            for (size_t pp = 0; pp < reached.size(); pp++) {
              if (reached[pp] || (pp == qq && viaTo.first == U'\0')) {
              // Needed due to the equivalence of standing still to “taking” an ε-transition.
              newTr[*(pairToName[q][qq])][viaTo.first].insert(*(pairToName[p][pp]));
              }
            }
          }
        }
      }
    }
    for (auto & fromVia : newTr) {
      auto const& from = fromVia.first;
      auto to = fromVia.second.find(U'\0');
      to->second.erase(from);
      if (to->second.empty()) {
        fromVia.second.erase(to);
      }
    }
    p->transitions = newTr;
    p->acceptingStates = newAcc;
    p->initial = *(pairToName[0][0]);
  }
  return *this;
}

makeInitial()

nfa::builder & reg::nfa::builder::makeInitial

(

std::string const &

state

)

Resets the initial state for the prospective NFA.

Parameters

state

the new initial state

Returns

reference to this object, for chaining operations

Definition at line 563 of file nfa.cpp.

                                                       {
  p->initial = state;
  p->transitions[state];
  return *this;
}

normalizeStateNames()

nfa::builder & reg::nfa::builder::normalizeStateNames

(

std::string const &

prefix

)

Reduces the prospective NFA's state names to consecutive numbers, prefixed with a given string.

Definition at line 592 of file nfa.cpp.

                                                                {
  if (!p->transitions.empty()) {
    vector<string> stateNames;
    stateNames.reserve(p->transitions.size());
    stateNames.push_back(p->initial);
    for (auto const& fromTo : p->transitions) {
      if (fromTo.first != p->initial) {
        stateNames.push_back(fromTo.first);
      }
    }
    Ntransitionmap newTr(p->transitions.size());
    unordered_set<string> newAcc(p->acceptingStates.size());
    for (size_t q = 0; q < stateNames.size(); q++) {
      auto const& vias = p->transitions[stateNames[q]];
      unordered_map<char32_t,unordered_set<string>> newVias(vias.size());
      for (auto const& viaTo : vias) {
        unordered_set<string> newTos(viaTo.second.size());
        for (size_t p = 0; p < stateNames.size(); p++) {
          if (viaTo.second.find(stateNames[p]) != viaTo.second.cend()) {
            newTos.insert(string(prefix).append(std::to_string(p)));
          }
        }
        newVias.insert(make_pair(viaTo.first, newTos));
      }
      newTr.insert(make_pair(string(prefix).append(std::to_string(q)), newVias));
      if (p->acceptingStates.find(stateNames[q]) != p->acceptingStates.end()) {
        newAcc.insert(string(prefix).append(std::to_string(q)));
      }
    }
    p->initial = string(string(prefix).append("0"));
    p->transitions = newTr;
    p->acceptingStates = newAcc;
  }
  return *this;
}

operator=() [1/2]

nfa::builder & reg::nfa::builder::operator=

(

builder const &

b

)

Copy-assigns a builder by copying another one's private implementation object.

Definition at line 507 of file nfa.cpp.

                                                  {
  if (this != &b) {
    p.reset(new pImpl(*(b.p)));
  }
  return *this;
}

operator=() [2/2]

nfa::builder & reg::nfa::builder::operator=

(

nfa::builder &&

b

)

Move-assigns a builder by stealing another one's private implementation object.

The other builder will be blank afterwards.

Definition at line 516 of file nfa.cpp.

                                                {
  if (this != &b) {
    p.reset(new pImpl);
    p.swap(b.p);
  }
  return *this;
}

setAccepting()

nfa::builder & reg::nfa::builder::setAccepting	(	std::string const &	state,
		bool	accept
	)

Sets whether or not a state will be accepting within the prospective NFA.

Parameters

state	the state's name
accept	true if the state should be an accept state afterwards, false else

Returns

reference to this object, for chaining operations

Definition at line 545 of file nfa.cpp.

                                                                     {
  if (p->transitions.empty()) {
    p->initial = state;
  }
  p->transitions[state];
  if (accept) {
    p->acceptingStates.insert(state);
  } else {
    p->acceptingStates.erase(state);
  }
  return *this;
}

unite()

nfa::builder & reg::nfa::builder::unite

(

nfa const &

other

)

Makes the prospective NFA also accept every word of another NFA's language.

Prepends the names of states defined so far with a single 1 and the other NFA's state names with a single 2 and adds a new initial state with an ε transition to each of the other initial states.

Parameters

other

the NFA whose language should also be accepted

Returns

reference to this object, for chaining operations

Definition at line 636 of file nfa.cpp.

                                              {
  string newInitial("q0");
  if (!p->transitions.empty()) {
    Ntransitionmap tempTr(p->transitions.size());
    for (auto const& fromVia : p->transitions) {
      unordered_map<char32_t,unordered_set<string>> tempVia(fromVia.second.size());
      for (auto const& viaTo : fromVia.second) {
        unordered_set<string> tempTo(viaTo.second.size());
        for (auto const& to : viaTo.second) {
          tempTo.insert(string(to.length() + 1, '1').replace(1, string::npos, to));
        }
        tempVia.insert(make_pair(viaTo.first, tempTo));
      }
      tempTr.insert(make_pair(string(fromVia.first.length() + 1, '1').replace(1, string::npos, fromVia.first), tempVia));
    }
    p->transitions = tempTr;
    unordered_set<string> tempAcc(p->acceptingStates.size());
    for (auto const& acc : p->acceptingStates) {
      tempAcc.insert(string(acc.length() + 1, '1').replace(1, string::npos, acc));
    }
    p->acceptingStates = tempAcc;
    p->initial = string(p->initial.length() + 1, '1').replace(1, string::npos, p->initial);
    addTransition(newInitial, p->initial, U'\0');
  }
  makeInitial(newInitial);
  auto & oAlphabet = other.getAlphabet();
  p->alphabet.insert(oAlphabet.cbegin(), oAlphabet.cend());
  for (size_t q = 0; q < other.getNumberOfStates(); q++) {
    auto & qLabel = other.getLabelOf(q);
    string newQLabel = string(qLabel.length() + 1, '2').replace(1, string::npos, qLabel);
    unordered_map<char32_t,unordered_set<string>> tempVia(oAlphabet.size() + 1);
    for (char32_t symbol : oAlphabet) {
      valarray<bool> const& to = other.delta(q, symbol);
      unordered_set<string> tempTo(other.getNumberOfStates());
      for (size_t p = 0; p < other.getNumberOfStates(); p++) { if (to[p]) {
        auto & pLabel = other.getLabelOf(p);
        tempTo.insert(string(pLabel.length() + 1, '2').replace(1, string::npos, pLabel));
      }}
      tempVia.insert(make_pair(symbol, tempTo));
    }
    p->transitions.insert(make_pair(newQLabel, tempVia));
    if (other.isAccepting(q)) {
      p->acceptingStates.insert(newQLabel);
    }
    if (q == 0) {
      addTransition(newInitial, newQLabel, U'\0');
    }
  }
  return *this;
}

---

The documentation for this class was generated from the following files:

• nfa.h
• nfa.cpp