reg::dfa::builder Class Reference

Constructs DFAs step by step. More...

#include <dfa.h>

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

Public Member Functions
	builder ()
	Constructs a blank builder object. 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 (nfa const &nfa)
	Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a DFA resulting from a powerset construction. 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= (const builder &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 DFA's alphabet. More...
builder &	addSymbol (std::string const &utf8Symbol)
	Same as above for a 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 DFA. More...
builder &	makeInitial (std::string const &state)
	Resets the initial state for the prospective DFA. More...
builder &	defineTransition (std::string const &from, std::string const &to, char32_t symbol)
	(Re-)Defines a transition for the prospective DFA. More...
builder &	defineTransition (std::string const &from, std::string const &to, std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
builder &	merge ()
	Merges the prospective DFA's indistinguishable states, allowing for minimization. More...
builder &	purge ()
	Purges the prospective DFA of unreachable and non-producing states, allowing for minimization. More...
builder &	minimize ()
	Convenience method for chaining purge and merge to achieve proper minimization. More...
builder &	unite (dfa const &other)
	Makes the prospective DFA also accept every word of another DFA's language. More...
builder &	intersect (dfa const &other)
	Makes the prospective DFA accept only words accepted also by another DFA. More...
builder &	complement ()
	Inverts the prospective DFA's language with respect to all possible strings over its alphabet. More...
builder &	normalizeStateNames (std::string const &prefix)
	Reduces the prospective NFA's state names to consecutive numbers, prefixed with a given string. More...
dfa	build ()
	Builds the DFA, as defined by previous operations, including completion. More...

Detailed Description

Constructs DFAs 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 72 of file dfa.h.

Constructor & Destructor Documentation

builder() [1/5]

reg::dfa::builder::builder

(

)

Constructs a blank builder object.

Definition at line 571 of file dfa.cpp.

: p(new pImpl) {}

builder() [2/5]

reg::dfa::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.

Definition at line 574 of file dfa.cpp.

                                  {
  auto initial = dfa.getLabelOf(0);
  auto alphabet = unordered_set<char32_t>(dfa.getAlphabet().begin(), dfa.getAlphabet().end());
  auto labels = unordered_set<string>(dfa.getNumberOfStates());
  auto transitions = Dtransitionmap(dfa.getNumberOfStates());
  p = make_unique<pImpl>(initial, alphabet, labels, transitions);
  for (size_t q = 0; q < dfa.getNumberOfStates(); ++q) {
    for (char32_t symbol : dfa.getAlphabet()) {
      defineTransition(dfa.getLabelOf(q), dfa.getLabelOf(dfa.delta(q, symbol)), symbol);
    }
    setAccepting(dfa.getLabelOf(q), dfa.isAccepting(q));
  }
}

builder() [3/5]

reg::dfa::builder::builder

(

nfa const &

nfa

)

Constructs a builder object with exactly the same states, symbols, transitions, initial state and accept states as a DFA resulting from a powerset construction.

Definition at line 589 of file dfa.cpp.

                                  {
  unordered_set<valarray<bool>> done;
  forward_list<valarray<bool>> stack(1, nfa.epsilonClosure(0));
  size_t stackSize(1);
  auto initial = nfa.getLabelOf(stack.front());
  auto alphabet = nfa.getAlphabet();
  alphabet.erase(alphabet.begin());
  unordered_set<char32_t> alphabetS(alphabet.begin(), alphabet.end());
  unordered_set<string> acceptingStates;
  Dtransitionmap transitions;
  transitions[initial];
  p = make_unique<pImpl>(initial, alphabetS, acceptingStates, transitions);
  while (stackSize != 0) {
    valarray<bool> current(move(stack.front()));
    stack.pop_front();
    stackSize--;
    for (char32_t symbol : p->alphabet) {
      valarray<bool> next(nfa.deltaHat(current, u32string(1, symbol)));
      defineTransition(nfa.getLabelOf(current), nfa.getLabelOf(next), symbol);
      auto equalToNext = [&](valarray<bool> const& ref)->bool{return (next == ref).min() == true;};
      if (!equalToNext(current) &&
          none_of(stack.begin(), stack.end(), equalToNext) &&
          none_of(done.begin(), done.end(), equalToNext)) {
        stack.push_front(next);
        stackSize++;
      }
    }
    for (size_t qi(0); qi < current.size(); qi++) {
      if (current[qi] && nfa.isAccepting(qi)) {
        setAccepting(nfa.getLabelOf(current), true);
        break;
      }
    }
    done.insert(current);
  }
}

builder() [4/5]

reg::dfa::builder::builder

(

builder const &

b

)

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

Definition at line 627 of file dfa.cpp.

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

builder() [5/5]

reg::dfa::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 631 of file dfa.cpp.

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

Member Function Documentation

addSymbol() [1/2]

dfa::builder & reg::dfa::builder::addSymbol

(

char32_t

symbol

)

Adds a symbol to the prospective DFA's alphabet.

Parameters

symbol

the symbol to add

Returns

reference to this object, for chaining operations

Definition at line 658 of file dfa.cpp.

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

addSymbol() [2/2]

dfa::builder & reg::dfa::builder::addSymbol

(

std::string const &

utf8Symbol

)

Same as above for a 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 664 of file dfa.cpp.

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

build()

dfa reg::dfa::builder::build

(

)

Builds the DFA, as defined by previous operations, including completion.

Returns

a DFA object with exactly the states, alphabet and transitions that were defined and a trash state if needed

Definition at line 1035 of file dfa.cpp.

                      {
  vector<char32_t> alphabetV(p->alphabet.begin(), p->alphabet.end());
  std::sort(alphabetV.begin(), alphabetV.end());
  p->complete();
  vector<string> labelV;
  labelV.reserve(p->transitions.size());
  labelV.push_back(p->initial);
  for (auto const& tr : p->transitions) {
    if (tr.first == p->initial) {
      continue;
    }
    labelV.push_back(tr.first);
  }
  valarray<bool> acceptingV(false, labelV.size());
  vector<vector<size_t>> transitionV(labelV.size(), vector<size_t>(alphabetV.size()));
  for (size_t q(0); q < labelV.size(); q++) {
    string const& qLabel = labelV[q];
    acceptingV[q] = (p->acceptingStates.find(qLabel) != p->acceptingStates.end());
    for (size_t s(0); s < alphabetV.size(); s++) {
      transitionV[q][s] = index_of(labelV, p->transitions[qLabel][alphabetV[s]]);
    }
  }
  return {alphabetV, transitionV, labelV, acceptingV};
}

complement()

dfa::builder & reg::dfa::builder::complement

(

)

Inverts the prospective DFA's language with respect to all possible strings over its alphabet.

Definition at line 990 of file dfa.cpp.

                                   {
  p->complete();
  for (auto const& fromVia : p->transitions) {
    if (!p->acceptingStates.erase(fromVia.first)) {
      p->acceptingStates.insert(fromVia.first);
    }
  }
  return *this;
}

defineTransition() [1/2]

dfa::builder & reg::dfa::builder::defineTransition	(	std::string const &	from,
		std::string const &	to,
		char32_t	symbol
	)

(Re-)Defines a transition for the prospective DFA.

If there's already a transition defined from from to to, it will be redefined with the new symbol.

Parameters

from	the starting state for the transition
to	the destination state for the transition
symbol	the symbol triggering the transition

Returns

reference to this object, for chaining operations

Definition at line 708 of file dfa.cpp.

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

defineTransition() [2/2]

dfa::builder & reg::dfa::builder::defineTransition	(	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 719 of file dfa.cpp.

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

intersect()

dfa::builder & reg::dfa::builder::intersect

(

dfa const &

other

)

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

Concatenates the names of states defined so far with the other DFA'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 933 of file dfa.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());
    Dtransitionmap 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);
        }
      }
    }
    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) {
        size_t p = index_of(stateNames, viaTo.second);
        for (size_t qq = 0; qq < other.getNumberOfStates(); qq++) {
          size_t pp = other.delta(qq, viaTo.first);
          newTr[*(pairToName[q][qq])][viaTo.first] = *(pairToName[p][pp]);
        }
      }
    }
    p->transitions = newTr;
    p->acceptingStates = newAcc;
    p->initial = *(pairToName[0][0]);
  }
  return *this;
}

makeInitial()

dfa::builder & reg::dfa::builder::makeInitial

(

std::string const &

state

)

Resets the initial state for the prospective DFA.

Parameters

state

the new initial state

Returns

reference to this object, for chaining operations

Definition at line 692 of file dfa.cpp.

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

merge()

dfa::builder & reg::dfa::builder::merge

(

)

Merges the prospective DFA's indistinguishable states, allowing for minimization.

This method doesn't change the prospective DFA's accepted language, but it will be built with the minimum of reachable states to fulfill that purpose. Unreachable states will be merged since they are indistinguishable, but they won't be removed, hence preventing true minimization; that's what purge is for.

Returns

reference to this object, for chaining operations

Definition at line 733 of file dfa.cpp.

                              {
  p->complete();
  vector<vector<size_t>> tTable(p->transitions.size());
  valarray<bool> accepting(false, p->transitions.size());
  vector<char32_t> sortedAlphabet(p->alphabet.begin(), p->alphabet.end());
  std::sort(sortedAlphabet.begin(), sortedAlphabet.end());
  vector<string> orderedStates;
  orderedStates.reserve(p->transitions.size());
  orderedStates.push_back(p->initial);
  for (auto const& entry : p->transitions) {
    if (entry.first != p->initial) {
      orderedStates.push_back(entry.first);
    }
  }
  for (size_t q(0); q < orderedStates.size(); q++) {
    string const& qLabel(orderedStates[q]);
    if (p->acceptingStates.find(qLabel) != p->acceptingStates.end()) {
      accepting[q] = true;
    }
    for (size_t s(0); s < sortedAlphabet.size(); s++) {
      tTable[q].push_back(index_of(orderedStates, p->transitions[qLabel][sortedAlphabet[s]]));
    }
  }
  vector<valarray<bool>> equivalences(dfa::pImpl::indistinguishableStates(tTable, accepting));
  for (size_t q(0); q < orderedStates.size(); q++) {
    for (size_t first(0); first < equivalences[q].size(); first++) {
      if (equivalences[q][first] && q > first) {
        string const& superfluous(orderedStates[q]);
        string const& remaining(orderedStates[first]);
        p->acceptingStates.erase(superfluous);
        p->transitions.erase(superfluous);
        for (auto& from : p->transitions) {
          for (auto& via : from.second) {
            if (via.second == superfluous) {
              via.second = remaining;
            }
          }
        }
        break;
      }
    }
  }
  return *this;
}

minimize()

dfa::builder & reg::dfa::builder::minimize

(

)

Convenience method for chaining purge and merge to achieve proper minimization.

Definition at line 844 of file dfa.cpp.

                                 {
  return purge().merge();
}

normalizeStateNames()

dfa::builder & reg::dfa::builder::normalizeStateNames

(

std::string const &

prefix

)

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

Definition at line 1001 of file dfa.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);
      }
    }
    Dtransitionmap 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,string> newVias(vias.size());
      for (auto const& viaTo : vias) {
        newVias.insert(make_pair(viaTo.first, prefix + to_string(index_of(stateNames, viaTo.second))));
      }
      newTr.insert(make_pair(prefix + to_string(q), newVias));
      if (p->acceptingStates.find(stateNames[q]) != p->acceptingStates.end()) {
        newAcc.insert(prefix + to_string(q));
      }
    }
    p->initial = prefix + "0";
    p->transitions = newTr;
    p->acceptingStates = newAcc;
  }
  return *this;
}

operator=() [1/2]

dfa::builder & reg::dfa::builder::operator=

(

const builder &

b

)

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

Definition at line 634 of file dfa.cpp.

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

operator=() [2/2]

dfa::builder & reg::dfa::builder::operator=

(

dfa::builder &&

b

)

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

The other builder will be blank afterwards.

Definition at line 643 of file dfa.cpp.

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

purge()

dfa::builder & reg::dfa::builder::purge

(

)

Purges the prospective DFA of unreachable and non-producing states, allowing for minimization.

This method doesn't change the prospective DFA's accepted language, but it will be built without states that will never be reached.

Returns

reference to this object, for chaining operations

Definition at line 785 of file dfa.cpp.

                              {
  unordered_set<string> reachable(&(p->initial), &(p->initial)+1);
  unordered_set<string> newReachable(reachable);
  while (newReachable.size() > 0) {
    unordered_set<string> oldReachable(move(newReachable));
    newReachable.clear();
    for (string const& reachableState : oldReachable) {
      for (auto const& reachedState : p->transitions[reachableState]) {
        if (reachable.insert(reachedState.second).second) {
          newReachable.insert(reachedState.second);
        }
      }
    }
  }
  for (auto it = p->transitions.begin(); it != p->transitions.end(); ) {
    if (reachable.find(it->first) == reachable.end()) {
      p->acceptingStates.erase(it->first);
      it = p->transitions.erase(it);
    } else {
      it++;
    }
  }
  unordered_set<string> producing(p->acceptingStates);
  unordered_set<string> newProducing(producing);
  while (newProducing.size() > 0) {
    unordered_set<string> oldProducing(move(newProducing));
    newProducing.clear();
    for (auto const& from : p->transitions) {
      for (auto const& via : from.second) {
        if (producing.find(via.second) != producing.end()) {
          if (producing.insert(from.first).second) {
            newProducing.insert(from.first);
          }
          break;
        }
      }
    }
  }
  for (auto it = p->transitions.begin(); it != p->transitions.end(); ) {
    if (producing.find(it->first) == producing.end() && it->first != p->initial) {
      p->acceptingStates.erase(it->first);
      for (auto& via : p->transitions) {
        for (auto itv = via.second.begin(); itv != via.second.end(); ) {
          if (itv->second == it->first) {
            itv = via.second.erase(itv);
          } else {
            itv++;
          }
        }
      }
      it = p->transitions.erase(it);
    } else {
      it++;
    }
  }
  return *this;
}

setAccepting()

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

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

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 674 of file dfa.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()

dfa::builder & reg::dfa::builder::unite

(

dfa const &

other

)

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

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

Parameters

other

the DFA whose language should also be accepted

Returns

reference to this object, for chaining operations

Definition at line 855 of file dfa.cpp.

                                              {
  if (!p->transitions.empty()) {
    auto const& oAlph = other.getAlphabet();
    for (char32_t symbol : oAlph) {
      addSymbol(symbol);
    }
    size_t trash = other.getNumberOfStates() * !!(p->alphabet.size() - oAlph.size());
    p->complete();
    vector<string> stateNames;
    stateNames.reserve(p->transitions.size());
    stateNames.push_back(p->initial);
    for (auto const& fromVia : p->transitions) {
      if (fromVia.first != p->initial) {
        stateNames.push_back(fromVia.first);
      }
    }
    Dtransitionmap 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() + !!trash; qq++) {
        string potentialName = stateNames[q];
        try {
          potentialName.append(other.getLabelOf(qq));
        } catch (std::out_of_range e) {
          // We hit the trash state.
        }
        for (auto nameIt = newTr.find(potentialName); nameIt != newTr.end(); nameIt = newTr.find(potentialName)) {
          potentialName.append("_");
        }
        auto nameIt = newTr.emplace(potentialName, p->alphabet.size());
        pairToName.emplace(q, 1).first->second.emplace(qq, &(nameIt.first->first));
        try {
          if (p->acceptingStates.find(stateNames[q]) != p->acceptingStates.end() || other.isAccepting(qq)) {
            newAcc.insert(potentialName);
          }
        } catch (std::out_of_range e) {
          // We hit the trash state AND q is not accepting.
        }
      }
    }
    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) {
        size_t p = index_of(stateNames, viaTo.second);
        for (size_t qq = 0; qq < other.getNumberOfStates() + !!trash; qq++) {
          size_t pp;
          try {
            pp = other.delta(qq, viaTo.first);
          } catch (std::logic_error e) {
            pp = trash;
          }
          newTr[*(pairToName[q][qq])][viaTo.first] = *(pairToName[p][pp]);
        }
      }
    }
    p->transitions = newTr;
    p->acceptingStates = newAcc;
    p->initial = *(pairToName[0][0]);
  } else {
    for (size_t q = 0; q < other.getNumberOfStates(); ++q) {
      for (char32_t symbol : other.getAlphabet()) {
        defineTransition(other.getLabelOf(q), other.getLabelOf(other.delta(q, symbol)), symbol);
      }
      setAccepting(other.getLabelOf(q), other.isAccepting(q));
    }
  }
  return *this;
}

---

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

• dfa.h
• dfa.cpp