nfa.cpp

Go to the documentation of this file.

#include "nfa.h"
using std::valarray;
using std::vector;
using std::string;
using std::make_unique;
using std::make_pair;
using std::u32string;

using std::move;

#include <unordered_set>
using std::unordered_set;

#include <unordered_map>
using std::unordered_map;

#include <algorithm>
using std::find;

#include <iterator>

#include "dfa.h"
#include "expression.h"

namespace reg {

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

  pImpl() :
      equivalent(),
      accepting(),
      alphabet(1, U'\0'),
      utf8Alphabet(1, ""),
      epsClosures(),
      labels(),
      transitions() {}

  pImpl(vector<char32_t>& alphabet, vector<vector<valarray<bool>>>& transitions,
      vector<string>& labels, valarray<bool>& acceptingStates) :
      accepting(move(acceptingStates)),
      alphabet(move(alphabet)),
      labels(move(labels)),
      transitions(move(transitions)) {
    utf8Alphabet.reserve(this->alphabet.size());
    for (char32_t symbol : this->alphabet) {
      if (symbol == U'\0') {
        utf8Alphabet.push_back("");
      } else {
        utf8Alphabet.push_back(converter.to_bytes(symbol));
      }
    }
    epsClosures = vector<valarray<bool>>(pImpl::labels.size());
  }


  dfa const& getEquivalentDfa(nfa const* owner) {
    if (!equivalent) {
      equivalent.reset(new dfa(dfa::builder(*owner).minimize()));
    }
    return *equivalent;
  }
};

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

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

bool nfa::operator==(nfa const& n) const {
  return p->getEquivalentDfa(this) == n.p->getEquivalentDfa(&n);
}

bool nfa::operator!=(nfa const& n) const {
  return p->getEquivalentDfa(this) != n.p->getEquivalentDfa(&n);
}


valarray<bool> const& nfa::delta(size_t q, char32_t symbol) const {
  size_t i = index_of(p->alphabet, symbol);
  if (i >= p->alphabet.size()) {
    #ifdef __EXCEPTIONS
    throw std::domain_error(
      string(u8"δ is not defined for symbol ") + converter.to_bytes(symbol)
    );
    #endif
  }
  if (q >= p->labels.size()) {
    #ifdef __EXCEPTIONS
    throw std::out_of_range(
      string("There is no state with index ").append(std::to_string(q))
    );
    #endif
  }
  return p->transitions[q][i];
}

valarray<bool> const& nfa::delta(size_t q, string const& utf8Symbol) const {
  return delta(q, converter.from_bytes(utf8Symbol)[0]);
}


valarray<bool> nfa::deltaHat(size_t q, std::u32string const& word) const {
  valarray<bool> qs(p->labels.size());
  qs[q] = true;
  return deltaHat(qs, word);
}

valarray<bool> nfa::deltaHat(size_t q, string const& utf8Word) const {
  return deltaHat(q, converter.from_bytes(utf8Word));
}


valarray<bool> nfa::deltaHat(valarray<bool> const& qs, std::u32string const& word) const {
  valarray<bool> ps = epsilonClosure(qs);
  for (char32_t symbol : word) {
    valarray<bool> reached(p->labels.size());
    size_t qi(0);
    for (bool qb : ps) {
      if (qb) {
        reached |= epsilonClosure(delta(qi, symbol));
      }
      qi++;
    }
    ps = move(reached);
  }
  return ps;
}

valarray<bool> nfa::deltaHat(valarray<bool> const& qs, string const& utf8Word) const {
  return deltaHat(qs, converter.from_bytes(utf8Word));
}


u32string nfa::getShortestWord() const {
  if (p->accepting[0]) {
    return U"";
  }
  unordered_map<size_t, u32string> shortestWords(p->labels.size());
  shortestWords.emplace(0, U"");
  while (true) {
    for (auto const& stateWord : shortestWords) {
      for (auto symbol : p->alphabet) {
        valarray<bool> reached = deltaHat(stateWord.first, u32string(!!symbol, symbol));
        u32string shWord = stateWord.second + u32string(!!symbol, symbol);
        for (size_t q = 0; q < reached.size(); q++) { if (reached[q]) {
          if (p->accepting[q]) {
            return shWord;
          }
          if (shortestWords.find(q) == shortestWords.end()) {
            shortestWords.emplace(q, shWord);
          }
        }}
      }
    }
  }
}

string nfa::getShortestUtf8Word() const {
  return converter.to_bytes(getShortestWord());
}


valarray<bool> const& nfa::epsilonClosure(size_t q) const {
  if (p->epsClosures[q].size() == 0) {
    p->epsClosures[q].resize(p->labels.size());
    p->epsClosures[q][q] = true;
    int growth(1);
    while (growth > 0) {
      growth = 0;
      valarray<bool> old(p->epsClosures[q]);
      size_t qi(0);
      for (bool qb : old) {
        if (qb) {
          size_t pi(0);
          for (bool pb : p->transitions[qi][0]) {
            if (pb) {
              if (!p->epsClosures[q][pi]) {
                growth++;
                p->epsClosures[q][pi] = true;
              }
            }
            pi++;
          } // going through the true bools in transitions[qi][0]
        }
        qi++;
      } // going through the true bools in old
    }
  }
  return p->epsClosures[q];
}


valarray<bool> nfa::epsilonClosure(valarray<bool> const& qs) const {
  valarray<bool> closure(p->labels.size());
  size_t qi(0);
  for (bool qb : qs) {
    if (qb) {
      closure |= epsilonClosure(qi);
    }
    qi++;
  } // going through the true bools in qs
  return closure;
}


string const& nfa::getLabelOf(size_t q) const {
  return p->labels[q];
}


string nfa::getLabelOf(valarray<bool> const& qs) const {
  string label;
  size_t qi(0);
  for (bool qb : qs) {
    if (qb) {
      label = label.append(1, label.length() == 0 ? '{' : ',');
      label = label.append(p->labels[qi]);
    }
    qi++;
  }
  if (label.length() == 0) {
    return string("{}");
  } else {
    return label.append(1, '}');
  }
}


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


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


size_t nfa::getNumberOfStates() const {
  return p->labels.size();
}


bool nfa::isAccepting(size_t q) const {
  return p->accepting[q];
}


bool nfa::hasAccepting(valarray<bool> const& qs) const {
  for (size_t q = 0; q < getNumberOfStates(); q++) {
    if (qs[q] && p->accepting[q]) {
      return true;
    }
  }
  return false;
}


nfa::builder nfa::unite(nfa const& n1, nfa const& n2) {
  return builder(n1).unite(n2);
}


nfa::builder nfa::intersect(nfa const& n1, nfa const& n2) {
  return builder(n1).intersect(n2);
}


nfa::builder nfa::subtract(nfa const& n1, nfa const& n2) {
  dfa::builder b2(n2);
  for (auto symbol : n1.getAlphabet()) {
    b2.addSymbol(symbol);
  }
  b2.complement().minimize();
  return builder(n1).intersect(builder(b2.build()).build());
}


nfa::builder nfa::complement(nfa const& n) {
  return nfa::builder(dfa::builder(n).complement().minimize().build());
}

nfa::nfa(nfa const& n) : p(new pImpl(*(n.p))) {}


nfa::nfa(nfa&& n) : p(new pImpl) {p.swap(n.p);}

nfa::nfa(nfa::builder& b) : nfa(b.build()) {}

nfa::nfa(dfa const& n) : nfa(builder(n).build()) {}

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


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

nfa::~nfa() = default;

using Ntransitionmap = unordered_map<string, unordered_map<char32_t, unordered_set<string>>>;

struct nfa::builder::pImpl {
  string initial; 
  unordered_set<string> acceptingStates; 
  unordered_set<char32_t> alphabet; 
  Ntransitionmap transitions;

  pImpl() = default;

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

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

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


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

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


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

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


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


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

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


nfa::builder& nfa::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;
}


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


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

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

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


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


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


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

nfa::builder::~builder() = default;
} // namespace reg