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 &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...
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 49 of file dfa.h.

Constructor & Destructor Documentation

builder() [1/5]

reg::dfa::builder::builder

(

)

Constructs a blank builder object.

Definition at line 437 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 440 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 = unordered_map<string,unordered_map<char32_t,string>>(dfa.getNumberOfStates());
  p = unique_ptr<pImpl>(new 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 460 of file dfa.cpp.

                                  {
  unordered_set<valarray<bool>, pImpl::ValarrayBoolHasher, pImpl::ValarrayBoolEqual> 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;
  unordered_map<string,unordered_map<char32_t,string>> transitions;
  transitions[initial];
  p = unique_ptr<pImpl>(new 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);
      pImpl::ValarrayBoolEqualTo equalToNext(next);
      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 &

b

)

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

Definition at line 503 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 507 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 535 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 541 of file dfa.cpp.

                                                          {
  return addSymbol(expression::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 726 of file dfa.cpp.

                      {
  vector<char32_t> alphabetV(p->alphabet.begin(), p->alphabet.end());
  sort(alphabetV.begin(), alphabetV.end());
  p->complete();
  vector<string> labelV;
  labelV.reserve(p->transitions.size());
  labelV.push_back(p->initial);
  valarray<bool> acceptingV(labelV.size(), false);
  for (auto const& tr : p->transitions) {
    if (tr.first == p->initial) {
      continue;
    }
    labelV.push_back(tr.first);
  }
  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] = distance(
          labelV.begin(),
          find(labelV.begin(), labelV.end(), p->transitions[qLabel][alphabetV[s]])
        );
    }
  }
  return {alphabetV, transitionV, labelV, acceptingV};
}

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 587 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 598 of file dfa.cpp.

                                                                                                       {
  return defineTransition(from, to, expression::converter->from_bytes(utf8Symbol)[0]);
}

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 571 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 611 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());
  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(distance(orderedStates.begin(), find(orderedStates.begin(), orderedStates.end(), 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;
}

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 510 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 519 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 663 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 552 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;
}

---

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

• dfa.h
• dfa.cpp