fabuilder.cpp

Go to the documentation of this file.

// Copyright 2017, 2018 Tom Kranz
//
// This file is part of reglibcpp.
//
// reglibcpp is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// reglibcpp is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with reglibcpp.  If not, see <https://www.gnu.org/licenses/>.

#include "fabuilder.h"

#include <forward_list>
#include <unordered_map>

#include "utils.h"

using std::forward_list;
using std::string;
using std::u32string;
using std::unordered_map;
using std::unordered_set;
using std::valarray;
using std::vector;

using std::move;

namespace reg {

struct fabuilder::impl {
  string const* initial = nullptr;
  unordered_set<char32_t> alphabet;
  unordered_map<string, unordered_map<char32_t, unordered_set<string const*>>>
      transitions;

  unordered_set<string const*> acceptingStates;


  string const* findStatePointer(string const& state) {
    return &(transitions.emplace(state, alphabet.size()).first->first);
  }


  string const* findStatePointer(string&& state) {
    return &(transitions.emplace(move(state), alphabet.size()).first->first);
  }

  bool isTrashState(string const* q) const {
    if (acceptingStates.count(q)) {
      return false;
    }
    auto const& from = transitions.at(*q);
    for (auto const& via : from) {
      if (via.second.size() > 1 ||
          (via.second.size() == 1 && !via.second.count(q))) {
        return false;
      }
    }
    return true;
  }

  string const* generateNewState() {
    size_t q(0);
    string const* newStateP = nullptr;
    while (newStateP == nullptr) {
      auto newStateIns =
          transitions.emplace("q" + std::to_string(q++), alphabet.size());
      if (newStateIns.second) {
        newStateP = &(newStateIns.first->first);
      }
    }
    if (transitions.size() == 1) {
      initial = newStateP;
    }
    return newStateP;
  }

  impl() = default;

  impl(impl const& other)
      : alphabet(other.alphabet),
        transitions(other.transitions.size()),
        acceptingStates(other.acceptingStates.size()) {
    for (auto const& from : other.transitions) {
      auto newFrom = transitions.emplace(from.first, from.second.size()).first;
      auto& newVias = newFrom->second;
      for (auto const& via : from.second) {
        auto& newTos =
            newVias.emplace(via.first, via.second.size()).first->second;
        for (string const* to : via.second) {
          newTos.emplace(findStatePointer(*to));
        }
      }
      if (other.acceptingStates.count(&(from.first))) {
        acceptingStates.emplace(&(newFrom->first));
      }
    }
    initial = findStatePointer(*(other.initial));
  }

  impl(nfa const& nfa)
      : alphabet(nfa.getAlphabet_().begin(), nfa.getAlphabet_().end()),
        transitions(nfa.getStates().size()),
        acceptingStates(nfa.getStates().size()) {
    auto const& alphabetV = nfa.getAlphabet_();
    auto const& statesV = nfa.getStates();
    initial = findStatePointer(nfa.getInitialState());
    for (size_t qi = 0; qi < statesV.size(); qi++) {
      auto qIt = transitions.emplace(statesV[qi], alphabetV.size()).first;
      for (size_t si = 0; si < alphabetV.size(); si++) {
        auto const& pis = nfa.delta(qi, si);
        auto sIt = qIt->second.emplace(alphabetV[si], statesV.size()).first;
        for (size_t pi = 0; pi < pis.size(); pi++) {
          if (pis[pi]) {
            sIt->second.emplace(findStatePointer(statesV[pi]));
          }
        }
      }
      if (nfa.isAccepting(qi)) {
        acceptingStates.emplace(&(qIt->first));
      }
    }
  }

  impl(dfa const& dfa)
      : alphabet(dfa.getAlphabet_().begin(), dfa.getAlphabet_().end()),
        transitions(dfa.getStates().size()),
        acceptingStates(dfa.getStates().size()) {
    auto const& alphabetV = dfa.getAlphabet_();
    auto const& statesV = dfa.getStates();
    initial = findStatePointer(dfa.getInitialState());
    for (size_t qi = 0; qi < statesV.size(); qi++) {
      auto qIt = transitions.emplace(statesV[qi], alphabetV.size()).first;
      for (size_t si = 0; si < alphabetV.size(); si++) {
        size_t pi = dfa.delta(qi, si);
        auto sIt = qIt->second.emplace(alphabetV[si], statesV.size()).first;
        sIt->second.emplace(findStatePointer(statesV[pi]));
      }
      if (dfa.isAccepting(qi)) {
        acceptingStates.emplace(&(qIt->first));
      }
    }
  }
};

fabuilder::fabuilder() : pim(new impl) {}

fabuilder::fabuilder(nfa const& nfa) : pim(new impl(nfa)) {}


fabuilder::fabuilder(dfa const& dfa) : pim(new impl(dfa)) {}

fabuilder::fabuilder(fabuilder const& b) : pim(new impl(*(b.pim))) {}


fabuilder::fabuilder(fabuilder&& b) : pim(new impl) { pim.swap(b.pim); }

fabuilder::~fabuilder() = default;

fabuilder& fabuilder::operator=(fabuilder const& b) {
  if (this != &b) {
    pim.reset(new impl(*(b.pim)));
  }
  return *this;
}


fabuilder& fabuilder::operator=(fabuilder&& b) {
  if (this != &b) {
    pim.reset(new impl());
    pim.swap(b.pim);
  }
  return *this;
}


fabuilder& fabuilder::setAccepting(std::string const& state, bool accept) {
  string const* stateP = pim->findStatePointer(state);
  if (pim->transitions.size() == 1) {
    pim->initial = stateP;
  }
  if (accept) {
    pim->acceptingStates.emplace(stateP);
  } else {
    pim->acceptingStates.erase(stateP);
  }
  return *this;
}


fabuilder& fabuilder::makeInitial(std::string const& state) {
  pim->initial = pim->findStatePointer(state);
  return *this;
}


fabuilder& fabuilder::addSymbol(std::string const& symbol) {
  return addSymbol_(converter.from_bytes(symbol)[0]);
}


fabuilder& fabuilder::addTransition(std::string const& from,
                                    std::string const& to,
                                    std::string const& symbol) {
  return addTransition_(from, to, converter.from_bytes(symbol)[0]);
}


fabuilder& fabuilder::addSymbol_(char32_t u32symbol) {
  pim->alphabet.emplace(u32symbol);
  return *this;
}


fabuilder& fabuilder::addTransition_(std::string const& from,
                                     std::string const& to,
                                     char32_t u32symbol) {
  auto fromIt = pim->transitions.emplace(from, pim->alphabet.size()).first;
  if (pim->transitions.size() == 1) {
    pim->initial = &(fromIt->first);
  }
  string const* toP = pim->findStatePointer(to);
  auto u32symbolIt = fromIt->second.emplace(u32symbol, 1).first;
  u32symbolIt->second.emplace(toP);
  addSymbol_(u32symbol);
  return *this;
}


fabuilder& fabuilder::powerset() {
  nfa nfa = buildNfa();
  pim->transitions.clear();
  pim->acceptingStates.clear();
  pim->alphabet.erase(U'\0');
  unordered_set<valarray<bool>> done;
  forward_list<valarray<bool>> stack(1, nfa.epsilonClosure(0));
  size_t stackSize(1);
  pim->initial = pim->findStatePointer(nfa.to_string(stack.front()));
  while (stackSize) {
    valarray<bool> current(move(stack.front()));
    stackSize--, stack.pop_front();
    auto currentIt =
        pim->transitions.emplace(nfa.to_string(current), pim->alphabet.size())
            .first;
    for (char32_t symbol : pim->alphabet) {
      valarray<bool> next(nfa.deltaHat_(current, u32string(1, symbol)));
      currentIt->second[symbol].emplace(
          pim->findStatePointer(nfa.to_string(next)));
      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++;
      }
    }
    if (nfa.isAccepting(current)) {
      pim->acceptingStates.emplace(&(currentIt->first));
    }
    done.insert(current);
  }
  return *this;
}


fabuilder& fabuilder::complete() {
  bool trashUsed(false);
  string const* trashState = [&] {
    for (auto const& entry : pim->transitions) {
      if (pim->isTrashState(&entry.first)) {
        trashUsed = true;
        return &entry.first;
      }
    }
    return pim->generateNewState();
  }();
  for (auto& from : pim->transitions) {
    for (char32_t symbol : pim->alphabet) {
      auto viaIt = from.second.emplace(symbol, 1).first;
      if (symbol == U'\0') {
        if (viaIt->second.empty()) {
          from.second.erase(viaIt);
        }
      } else {
        if (viaIt->second.empty()) {
          viaIt->second.emplace(trashState);
          trashUsed |= (&from.first != trashState);
        }
      }
    }
  }
  if (!trashUsed) {
    pim->transitions.erase(*trashState);
  }
  pim->alphabet.erase(U'\0');
  return *this;
}


fabuilder& fabuilder::merge(bool force) {
  if (!hasNondeterminism()) {
    complete();
  } else {
    purge();
    if (!hasNondeterminism()) {
      complete();
    } else if (force) {
      powerset();
    } else {
      throw nondeterminism_exception();
    }
  }
  vector<vector<size_t>> tTable(pim->transitions.size());
  valarray<bool> accepting(false, pim->transitions.size());
  vector<char32_t> sortedAlphabet(pim->alphabet.begin(), pim->alphabet.end());
  std::sort(sortedAlphabet.begin(), sortedAlphabet.end());
  vector<string const*> orderedStates;
  orderedStates.reserve(pim->transitions.size());
  orderedStates.push_back(pim->initial);
  for (auto const& entry : pim->transitions) {
    if (&entry.first != pim->initial) {
      orderedStates.push_back(&entry.first);
    }
  }
  for (size_t qi(0); qi < orderedStates.size(); qi++) {
    string const* q(orderedStates[qi]);
    accepting[qi] = pim->acceptingStates.count(q);
    for (size_t si(0); si < sortedAlphabet.size(); si++) {
      tTable[qi].push_back(index_of(
          orderedStates, *(pim->transitions[*q][sortedAlphabet[si]].begin())));
    }
  }
  auto equivalences = dfa::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]);
        pim->acceptingStates.erase(superfluous);
        pim->transitions.erase(*superfluous);
        for (auto& from : pim->transitions) {
          for (auto& via : from.second) {
            auto supIt = via.second.find(superfluous);
            if (supIt != via.second.end()) {
              via.second.erase(supIt);
              via.second.insert(remaining);
            }
          }
        }
        break;
      }
    }
  }
  return *this;
}


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


fabuilder& fabuilder::minimize(bool force) { return merge(force).purge(); }


fabuilder& fabuilder::unite(nfa const& other) {
  if (!pim->transitions.empty()) {
    auto const& oAlph = other.getAlphabet_();
    for (char32_t symbol : oAlph) {
      addSymbol_(symbol);
    }
    size_t trash =
        other.getStates().size() * !!(pim->alphabet.size() - oAlph.size());
    complete();
    vector<string const*> stateNames;
    stateNames.reserve(pim->transitions.size());
    stateNames.push_back(pim->initial);
    for (auto const& fromVia : pim->transitions) {
      if (&(fromVia.first) != pim->initial) {
        stateNames.push_back(&(fromVia.first));
      }
    }
    unordered_map<string, unordered_map<char32_t, unordered_set<string const*>>>
        newTr(stateNames.size() * (other.getStates().size() + !!trash));
    unordered_set<string const*> newAcc(stateNames.size() *
                                        (other.getStates().size() + !!trash));
    unordered_map<size_t, unordered_map<size_t, string const*>> pairToName(
        stateNames.size());
    for (size_t q = 0; q < stateNames.size(); q++) {
      for (size_t qq = 0; qq < other.getStates().size() + !!trash; qq++) {
        string potentialName = *stateNames[q];
        if (qq < other.getStates().size()) {
          potentialName.append(other.getStates()[qq]);
        }
        while (newTr.count(potentialName)) {
          potentialName.append("_");
        }
        auto nameIt =
            newTr.emplace(move(potentialName), pim->alphabet.size()).first;
        pairToName.emplace(q, 1).first->second.emplace(qq, &(nameIt->first));
        if (pim->acceptingStates.count(stateNames[q]) ||
            (qq < other.getStates().size() && other.isAccepting(qq))) {
          newAcc.insert(&(nameIt->first));
        }
      }
    }
    valarray<bool> empty(other.getStates().size());
    for (char32_t symbol : pim->alphabet) {
      for (size_t q = 0; q < stateNames.size(); q++) {
        auto const& viaTo = pim->transitions[*stateNames[q]][symbol];
        for (size_t qq = 0; qq < other.getStates().size() + !!trash; qq++) {
          for (string const* pLabel : viaTo) {
            size_t p = index_of(stateNames, pLabel);
            valarray<bool> const* pps;
            try {
              pps = &other.delta_(qq, symbol);
            } catch (std::logic_error e) {
              pps = &empty;
            }
            if (!pps->max()) {
              newTr[*(pairToName[q][qq])][symbol].emplace(pairToName[p][trash]);
            } else {
              for (size_t pp = 0; pp < other.getStates().size(); pp++) {
                if ((*pps)[pp]) {
                  newTr[*(pairToName[q][qq])][symbol].emplace(
                      pairToName[p][pp]);
                }
              }
            }
          }
        }
      }
    }
    pim->transitions = move(newTr);
    pim->acceptingStates = move(newAcc);
    pim->initial = pairToName[0][0];
  } else {
    pim->alphabet.insert(other.getAlphabet_().begin(),
                         other.getAlphabet_().end());
    makeInitial(other.getInitialState());
    for (size_t q = 0; q < other.getStates().size(); ++q) {
      for (size_t si = 0; si < other.getAlphabet_().size(); si++) {
        auto const& reached = other.delta(q, si);
        for (size_t p = 0; p < other.getStates().size(); p++) {
          if (reached[q]) {
            addTransition_(other.getStates()[q], other.getStates()[p],
                           other.getAlphabet_()[si]);
          }
        }
      }
      setAccepting(other.getStates()[q], other.isAccepting(q));
    }
  }
  return *this;
}


fabuilder& fabuilder::intersect(nfa const& other) {
  if (!pim->transitions.empty()) {
    vector<string const*> stateNames;
    stateNames.reserve(pim->transitions.size());
    stateNames.emplace_back(pim->initial);
    for (auto const& fromTo : pim->transitions) {
      if (&(fromTo.first) != pim->initial) {
        stateNames.emplace_back(&(fromTo.first));
      }
    }
    auto const& oAlph = other.getAlphabet_();
    size_t commonSymbols = 0;
    for (char32_t symbol : pim->alphabet) {
      if (index_of(oAlph, symbol) < oAlph.size()) {
        commonSymbols++;
      } else {
        for (auto& fromVia : pim->transitions) {
          fromVia.second.erase(symbol);
        }
      }
    }
    pim->alphabet.insert(oAlph.begin(), oAlph.end());
    unordered_map<string, unordered_map<char32_t, unordered_set<string const*>>>
        newTr(stateNames.size() * other.getStates().size());
    unordered_set<string const*> newAcc(stateNames.size() *
                                        other.getStates().size());
    unordered_map<size_t, unordered_map<size_t, string const*>> pairToName(
        stateNames.size() * other.getStates().size());
    for (size_t q = 0; q < stateNames.size(); q++) {
      for (size_t qq = 0; qq < other.getStates().size(); qq++) {
        string potentialName = *stateNames[q] + other.getStates()[qq];
        while (newTr.count(potentialName)) {
          potentialName.append("_");
        }
        auto nameIt = newTr.emplace(move(potentialName), commonSymbols).first;
        pairToName.emplace(q, 1).first->second.emplace(qq, &(nameIt->first));
        if (pim->acceptingStates.count(stateNames[q]) &&
            other.isAccepting(qq)) {
          newAcc.emplace(&(nameIt->first));
        }
      }
      pim->transitions[*stateNames[q]][U'\0'].emplace(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& viaTos = pim->transitions[*stateNames[q]];
      for (auto const& viaTo : viaTos) {
        for (size_t qq = 0; qq < other.getStates().size(); qq++) {
          valarray<bool> const& reached = other.delta_(qq, viaTo.first);
          for (string 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(
                    &(newTr.find(*(pairToName[p][pp]))->first));
              }
            }
          }
        }
      }
    }
    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);
      }
    }
    pim->transitions = move(newTr);
    pim->acceptingStates = move(newAcc);
    pim->initial = pim->findStatePointer(*(pairToName[0][0]));
  }
  return *this;
}


fabuilder& fabuilder::subtract(nfa const& other, bool force) {
  for (char32_t symbol : other.getAlphabet_()) {
    addSymbol_(symbol);
  }
  return this->complement(force).unite(other).complement(force);
}


fabuilder& fabuilder::complement(bool force) {
  if (!hasNondeterminism()) {
    complete();
  } else {
    purge();
    if (!hasNondeterminism()) {
      complete();
    } else if (force) {
      powerset();
    } else {
      throw nondeterminism_exception();
    }
  }
  for (auto const& fromVia : pim->transitions) {
    if (!pim->acceptingStates.erase(&(fromVia.first))) {
      pim->acceptingStates.insert(&(fromVia.first));
    }
  }
  return *this;
}


fabuilder& fabuilder::normalizeStateNames(std::string const& prefix) {
  if (!pim->transitions.empty()) {
    vector<string const*> stateNames;
    stateNames.reserve(pim->transitions.size());
    stateNames.push_back(pim->initial);
    for (auto const& fromTo : pim->transitions) {
      if (&(fromTo.first) != pim->initial) {
        stateNames.push_back(&(fromTo.first));
      }
    }
    unordered_map<string, unordered_map<char32_t, unordered_set<string const*>>>
        newTr(pim->transitions.size());
    unordered_set<string const*> newAcc(pim->acceptingStates.size());
    string const* newInitial;
    for (size_t q = 0; q < stateNames.size(); q++) {
      auto const& vias = pim->transitions[*stateNames[q]];
      auto newIt = newTr.emplace(prefix + std::to_string(q), vias.size()).first;
      string const* newQ = &(newIt->first);
      auto& newVias = newIt->second;
      for (auto const& viaTo : vias) {
        auto& newTos =
            newVias.emplace(viaTo.first, viaTo.second.size()).first->second;
        for (size_t p = 0; p < stateNames.size(); p++) {
          if (viaTo.second.count(stateNames[p])) {
            newTos.emplace(
                &(newTr
                      .emplace(
                          prefix + std::to_string(p),
                          pim->transitions[*stateNames[p]][viaTo.first].size())
                      .first->first));
          }
        }
      }
      if (pim->acceptingStates.count(stateNames[q])) {
        newAcc.insert(newQ);
      }
      if (pim->initial == stateNames[q]) {
        newInitial = newQ;
      }
    }
    pim->initial = newInitial;
    pim->transitions = move(newTr);
    pim->acceptingStates = move(newAcc);
  }
  return *this;
}

bool fabuilder::isComplete() {
  for (auto const& from : pim->transitions) {
    for (char32_t symbol : pim->alphabet) {
      if (symbol == U'\0') {
        continue;
      }
      auto viaIt = from.second.find(symbol);
      if (viaIt == from.second.end() || viaIt->second.empty()) {
        return false;
      }
    }
  }
  return true;
}

bool fabuilder::hasNondeterminism() {
  for (auto const& from : pim->transitions) {
    for (auto const& via : from.second) {
      if ((via.first == U'\0' && !via.second.empty()) ||
          via.second.size() > 1) {
        return true;
      }
    }
  }
  return false;
}


nfa fabuilder::buildNfa() {
  if (pim->initial == nullptr) {
    pim->initial = &(pim->transitions.emplace("", 0).first->first);
  }
  vector<char32_t> alphabetV(pim->alphabet.begin(), pim->alphabet.end());
  if (!pim->alphabet.count(U'\0')) {
    alphabetV.emplace_back(U'\0');
  }
  std::sort(alphabetV.begin(), alphabetV.end());
  vector<string> labelV;
  labelV.reserve(pim->transitions.size());
  labelV.emplace_back(*pim->initial);
  valarray<bool> acceptingV(pim->transitions.size());
  acceptingV[0] = pim->acceptingStates.count(pim->initial);
  for (auto const& entry : pim->transitions) {
    if (&(entry.first) == pim->initial) {
      continue;
    }
    acceptingV[labelV.size()] = pim->acceptingStates.count(&(entry.first));
    labelV.emplace_back(entry.first);
  }
  vector<vector<valarray<bool>>> transitionV(
      labelV.size(),
      vector<valarray<bool>>(alphabetV.size(), valarray<bool>(labelV.size())));
  for (size_t qi(0); qi < labelV.size(); qi++) {
    auto const& fromQ = pim->transitions[labelV[qi]];
    for (size_t si(0); si < alphabetV.size(); si++) {
      auto viaIt = fromQ.find(alphabetV[si]);
      if (viaIt == fromQ.end()) {
        continue;
      }
      unordered_set<string const*> const& viaSymbol = viaIt->second;
      for (size_t pi(0); pi < labelV.size(); pi++) {
        transitionV[qi][si][pi] =
            viaSymbol.count(pim->findStatePointer(labelV[pi]));
      }
    }
  }
  return {move(alphabetV), move(transitionV), move(labelV), move(acceptingV)};
}


dfa fabuilder::buildDfa(bool force) {
  if (!hasNondeterminism()) {
    complete();
  } else {
    purge();
    if (!hasNondeterminism()) {
      complete();
    } else if (force) {
      powerset();
    } else {
      throw nondeterminism_exception();
    }
  }
  if (pim->initial == nullptr) {
    pim->initial = &(pim->transitions.emplace("", 0).first->first);
  }
  vector<char32_t> alphabetV(pim->alphabet.begin(), pim->alphabet.end());
  std::sort(alphabetV.begin(), alphabetV.end());
  vector<string> labelV;
  labelV.reserve(pim->transitions.size());
  labelV.emplace_back(*pim->initial);
  valarray<bool> acceptingV(pim->transitions.size());
  acceptingV[0] = pim->acceptingStates.count(pim->initial);
  for (auto const& entry : pim->transitions) {
    if (&(entry.first) == pim->initial) {
      continue;
    }
    acceptingV[labelV.size()] = pim->acceptingStates.count(&(entry.first));
    labelV.emplace_back(entry.first);
  }
  vector<vector<size_t>> transitionV(labelV.size(),
                                     vector<size_t>(alphabetV.size()));
  for (size_t qi(0); qi < labelV.size(); qi++) {
    auto const& fromQ = pim->transitions[labelV[qi]];
    for (size_t si(0); si < alphabetV.size(); si++) {
      auto viaIt = fromQ.find(alphabetV[si]);
      if (viaIt == fromQ.end() || viaIt->second.empty()) {
        continue;
      }
      unordered_set<string const*> const& viaSymbol = viaIt->second;
      transitionV[qi][si] = index_of(labelV, **viaSymbol.begin());
    }
  }
  return {move(alphabetV), move(transitionV), move(labelV), move(acceptingV)};
}

}  // namespace reg