dfa.cpp

Go to the documentation of this file.

#include "dfa.h"
using std::valarray;
using std::vector;
using std::string;
using std::to_string;
using std::make_unique;
using std::u32string;

using std::move;

#include <unordered_set>
using std::unordered_set;

#include <unordered_map>
using std::unordered_map;

#include <forward_list>
using std::forward_list;

#include <algorithm>
using std::find;
using std::none_of;

#include <cstdint>

#include "nfa.h"
#include "utils.h"

namespace std {
  template<>
  struct hash<valarray<bool>> {
    size_t operator()(valarray<bool> const&  value) const {
      size_t hash = 0;
      for (bool v : value) {
        hash <<= 1;
        hash |= v;
      }
      return hash;
    }
  };

  template<>
  struct equal_to<valarray<bool>> {
    bool operator()(valarray<bool> const& lhs, valarray<bool> const& rhs) const {
      return (lhs.size() == rhs.size() && (lhs == rhs).min() == true);
    }
  };
}

namespace reg {

struct dfa::pImpl {
  std::shared_ptr<nfa const> mutable equivalent; 
  valarray<bool> accepting; 
  vector<char32_t> alphabet; 
  vector<string> utf8Alphabet; 
  vector<string> labels; 
  vector<vector<size_t>> transitions; 

  pImpl() : accepting(false, 1), alphabet(0), utf8Alphabet(0), labels(1), transitions(1) {}

  pImpl(vector<char32_t>& alphabet, vector<vector<size_t>>& transitions,
        vector<string>& labels, valarray<bool>& accepting)  :
        accepting(move(accepting)),
        alphabet(move(alphabet)),
        labels(move(labels)),
        transitions(move(transitions)) {
    utf8Alphabet.reserve(this->alphabet.size());
    for (char32_t symbol : this->alphabet) {
      utf8Alphabet.push_back(converter.to_bytes(symbol));
    }
  }


  static vector<valarray<bool>> indistinguishableStates(
      vector<vector<size_t>> const& transitions, valarray<bool> const& accepting) {
    vector<valarray<bool>> distinguishable;
    distinguishable.reserve(transitions.size());
    for (size_t q(0); q < transitions.size(); q++) {
      bool qAcc(accepting[q]);
      distinguishable.push_back(valarray<bool>(false, transitions.size()));
      for (size_t p(0); p < q; p++) {
        bool pAcc(accepting[p]);
        distinguishable[q][p] = (qAcc != pAcc);
        distinguishable[p][q] = (qAcc != pAcc);
      }
    }
    bool changes(true);
    while (changes) {
      changes = false;
      for (size_t q(0); q < transitions.size(); q++) {
        for (size_t p(0); p < q; p++) {
          if (distinguishable[q][p]) {
            continue;
          }
          for (size_t s(0); s < transitions[q].size(); s++) {
            size_t qS(transitions[q][s]);
            size_t pS(transitions[p][s]);
            if (distinguishable[qS][pS]) {
              changes = true;
              distinguishable[q][p] = true;
              distinguishable[p][q] = true;
              break;
            }
          }
        }
      }
    }
    valarray<bool> allTrue(true, transitions.size());
    for (size_t i(0); i < distinguishable.size(); i++) {
      distinguishable[i] ^= allTrue;
    }
    return distinguishable;
  }
};

dfa::dfa() : p(new pImpl) {}

dfa::dfa(vector<char32_t>& alphabet,
         vector<vector<size_t>>& transitions,
         vector<string>& labels,
         valarray<bool>& acceptingStates) :
    p(make_unique<pImpl>(alphabet, transitions, labels, acceptingStates)) {}

dfa::dfa(dfa const& d) : p(new pImpl(*(d.p))) {}


dfa::dfa(dfa&& d) : p(new pImpl) {p.swap(d.p);}

dfa&  dfa::operator=(dfa const& d) {
  if (this != &d) {
    p.reset(new pImpl(*(d.p)));
  }
  return *this;
}


dfa&  dfa::operator=(dfa&& d) {
  if (this != &d) {
    p.reset(new pImpl);
    p.swap(d.p);
  }
  return *this;
}

dfa::~dfa() = default;

#ifndef DOXYGEN_SHOULD_SKIP_THIS
dfa::operator nfa const&() const {
  if (!p->equivalent) {
    p->equivalent = std::make_shared<nfa const>(nfa::builder(*this).build());
  }
  return *p->equivalent;
}
#endif // DOXYGEN_SHOULD_SKIP_THIS


bool dfa::operator==(dfa const& d) const {
  forward_list<char32_t> unitedAlphabet(p->alphabet.begin(), p->alphabet.end());
  size_t unitedAlphabetSize(p->alphabet.size());
  for (char32_t symbol : d.getAlphabet()) {
    if (find(p->alphabet.begin(), p->alphabet.end(), symbol) == p->alphabet.end()) {
      unitedAlphabet.push_front(symbol);
      unitedAlphabetSize++;
    }
  }
  vector<vector<size_t>> tTable(getNumberOfStates()+d.getNumberOfStates()+1, vector<size_t>(unitedAlphabetSize));
  valarray<bool> accepting(false, getNumberOfStates()+d.getNumberOfStates()+1);
  for (size_t q(0); q < getNumberOfStates(); q++) {
    size_t s(0);
    vector<size_t>& row = tTable[q];
    for (char32_t symbol : unitedAlphabet) {
      try {
        row[s] = delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      s++;
    }
    accepting[q] = isAccepting(q);
  }
  for (size_t q(0); q < d.getNumberOfStates(); q++) {
    size_t s(0);
    vector<size_t>& row = tTable[q+getNumberOfStates()];
    for (char32_t symbol : unitedAlphabet) {
      try {
        row[s] = getNumberOfStates()+d.delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      s++;
    }
    accepting[q+getNumberOfStates()] = d.isAccepting(q);
  }
  for (size_t s(0); s < unitedAlphabetSize; s++) {
    tTable[getNumberOfStates()+d.getNumberOfStates()][s] = getNumberOfStates()+d.getNumberOfStates();
  }
  return pImpl::indistinguishableStates(tTable, accepting)[0][getNumberOfStates()];
}

bool dfa::operator!=(dfa const& d) const {return !operator==(d);}

bool dfa::operator==(nfa const& n) const {
  return operator==(static_cast<dfa const&>(n));
}

bool dfa::operator!=(nfa const& n) const {return !operator==(n);}


size_t dfa::delta(size_t qi, size_t si) const {
  if (si >= p->alphabet.size()) {
    throw std::domain_error("There is no symbol with index " + to_string(si));
  }
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + to_string(qi));
  }
  return p->transitions[qi][si];
}


size_t dfa::delta(size_t qi, char32_t symbol) const {
  try {
    return delta(qi, index_of(p->alphabet, symbol));
  } catch (std::domain_error e) {
    throw std::domain_error(u8"δ is not defined for symbol " + converter.to_bytes(symbol));
  }
}

size_t dfa::delta(size_t qi, string const& utf8Symbol) const {
  return delta(qi, converter.from_bytes(utf8Symbol)[0]);
}


string const& dfa::delta(string const& q, char32_t symbol) const {
  try {
    return getStates()[delta(index_of(getStates(), q), symbol)];
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}

string const& dfa::delta(string const& q, string const& utf8Symbol) const {
  return delta(q, converter.from_bytes(utf8Symbol)[0]);
}


size_t dfa::deltaHat(size_t qi, u32string const& word) const {
  for (char32_t symbol : word) {
    qi = delta(qi, symbol);
  }
  return qi;
}

size_t dfa::deltaHat(size_t q, string const& utf8Word) const {
  return deltaHat(q, converter.from_bytes(utf8Word));
}


string const& dfa::deltaHat(string const& q, u32string const& word) const {
  return p->labels[deltaHat(index_of(getStates(), q), word)];
}

string const& dfa::deltaHat(string const& q, string const& utf8Word) const {
  return deltaHat(q, converter.from_bytes(utf8Word));
}

u32string dfa::getShortestWord() const {
  return findShortestWord(*this);
}

string dfa::getShortestUtf8Word() const {
  return findShortestUtf8Word(*this);
}

string const& dfa::getLabelOf(size_t q) const {
  return getStates().at(q);
}


string const& dfa::getInitialState() const {
  return getStates()[0];
}


vector<string> const& dfa::getStates() const {
  return p->labels;
}


vector<char32_t> const& dfa::getAlphabet() const {
  return p->alphabet;
}


vector<string> const& dfa::getUtf8Alphabet() const {
  return p->utf8Alphabet;
}

size_t dfa::getNumberOfStates() const {
  return getStates().size();
}

size_t dfa::getNumberOfSymbols() const {
  return getAlphabet().size();
}


bool dfa::isAccepting(size_t qi) const {
  if (qi >= p->labels.size()) {
    throw std::out_of_range("There is no state with index " + to_string(qi));
  }
  return p->accepting[qi];
}


bool dfa::isAccepting(string const& q) const {
  try {
    return isAccepting(index_of(getStates(), q));
  } catch (std::out_of_range e) {
    throw std::out_of_range("There is no state named " + q);
  }
}


u32string findShortestWord(dfa const& d) {
  auto const& p = d.p;
  if (p->accepting[0]) {
    return U"";
  }
  unordered_map<size_t, u32string> shortestWords(p->labels.size());
  size_t oldSize = 0;
  shortestWords.emplace(0, U"");
  while (shortestWords.size() > oldSize) {
    oldSize = shortestWords.size();
    for (auto const& stateWord : shortestWords) {
      for (auto symbol : p->alphabet) {
        size_t reached = d.delta(stateWord.first, symbol);
        u32string shWord = stateWord.second + symbol;
        if (p->accepting[reached]) {
          return shWord;
        }
        if (shortestWords.find(reached) == shortestWords.end()) {
          shortestWords.emplace(reached, shWord);
        }
      }
    }
  }
  throw std::logic_error("This DFA doesn't accept any words!");
}

string findShortestUtf8Word(dfa const& d) {
  return converter.to_bytes(findShortestWord(d));
}


dfa::builder dfa::unite(dfa const& d1, dfa const& d2) {
  return builder(d1).unite(d2);
}


dfa::builder dfa::intersect(dfa const& d1, dfa const& d2) {
  return builder(d1).intersect(d2);
}


dfa::builder dfa::subtract(dfa const& d1, dfa const& d2) {
  builder b1(d1);
  for (auto symbol : d2.getAlphabet()) {
    b1.addSymbol(symbol);
  }
  return b1.complement().unite(d2).complement();
}


dfa::builder dfa::complement(dfa const& d) {
  return dfa::builder(d).complement();
}

using Dtransitionmap = unordered_map<string, unordered_map<char32_t, string>>;

struct dfa::builder::pImpl {
  string initial; 
  unordered_set<char32_t> alphabet; 
  unordered_set<string> acceptingStates; 
  Dtransitionmap transitions;

  pImpl() = default;

  pImpl(
      string& initial,
      unordered_set<char32_t>& alphabet,
      unordered_set<string>& acceptingStates,
      Dtransitionmap& transitions
    ) : initial(move(initial)),
        alphabet(move(alphabet)),
        acceptingStates(move(acceptingStates)),
        transitions(move(transitions)) {}

  bool isTrashState(string const&  q) const {
    if (acceptingStates.count(q) != 0) {
      return false;
    }
    auto const& from = transitions.at(q);
    for (char32_t symbol : alphabet) {
      auto via = from.find(symbol);
      if (via != from.end() && (*via).second != q) {
        return false;
      }
    }
    return true;
  }

  string const& generateNewState() {
    size_t q(0);
    string newState;
    while (transitions.find(newState = "q" + to_string(q)) != transitions.end()) {
      q++;
    }
    if (transitions.empty()) {
      initial = newState;
    }
    return transitions.insert(std::make_pair(newState, unordered_map<char32_t, string>())).first->first;
  }


  void complete() {
    bool trashUsed(false);
    string const& trashState = [&]{
      for (auto const& entry : this->transitions) {
        if (this->isTrashState(entry.first)) {
          trashUsed = true;
          return entry.first;
        }
      }
      return this->generateNewState();
    }();
    for (auto& from : transitions) {
      for (char32_t symbol : alphabet) {
        if (from.second.find(symbol) == from.second.end()) {
          from.second[symbol] = trashState;
          trashUsed |= (from.first != trashState);
        }
      }
    }
    if (!trashUsed) {
      transitions.erase(trashState);
    }
  }
};

dfa::builder::builder() : p(new pImpl) {}

dfa::builder::builder(dfa const& dfa) {
  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));
  }
}

dfa::builder::builder(nfa const& nfa) {
  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);
  }
}

dfa::builder::builder(builder const& b) : p(new pImpl(*(b.p))) {}


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

dfa::builder&  dfa::builder::operator=(const builder& b) {
  if (this != &b) {
    p.reset(new pImpl(*(b.p)));
  }
  return *this;
}


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

dfa::builder::~builder() = default;

dfa::builder::operator dfa() {
  return build();
}


dfa::builder& dfa::builder::addSymbol(char32_t symbol) {
  p->alphabet.insert(symbol);
  return *this;
}

dfa::builder& dfa::builder::addSymbol(string const& utf8Symbol) {
  return addSymbol(converter.from_bytes(utf8Symbol)[0]);
}


dfa::builder& dfa::builder::setAccepting(string const& state, bool accept) {
  if (p->transitions.empty()) {
    p->initial = state;
  }
  p->transitions[state];
  if (accept) {
    p->acceptingStates.insert(state);
  } else {
    p->acceptingStates.erase(state);
  }
  return *this;
}


dfa::builder& dfa::builder::makeInitial(string const& state) {
  p->initial = state;
  p->transitions[state];
  return *this;
}


dfa::builder& dfa::builder::defineTransition(string const& from, string const& to, char32_t symbol) {
  if (p->transitions.empty()) {
    p->initial = from;
  }
  p->transitions[to];
  p->transitions[from][symbol] = to;
  addSymbol(symbol);
  return *this;
}

dfa::builder& dfa::builder::defineTransition(string const& from, string const& to, string const& utf8Symbol) {
  return defineTransition(from, to, converter.from_bytes(utf8Symbol)[0]);
}


dfa::builder& dfa::builder::merge() {
  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;
}


dfa::builder& dfa::builder::purge() {
  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;
}

dfa::builder& dfa::builder::minimize() {
  return purge().merge();
}


dfa::builder& dfa::builder::unite(dfa const& other) {
  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;
}


dfa::builder& dfa::builder::intersect(dfa const& other) {
  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;
}

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

dfa::builder& dfa::builder::normalizeStateNames(std::string const& prefix) {
  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;
}


dfa dfa::builder::build() {
  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};
}

} // namespace reg::dfa