dfa.cpp

Go to the documentation of this file.

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

using std::distance;
using std::to_string;
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::sort;
using std::none_of;

#include <cstdint>

#include "nfa.h"
#include "expression.h"

namespace reg {

struct dfa::pImpl {
  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(0) {}

  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(expression::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(unique_ptr<pImpl>(new pImpl(alphabet, transitions, labels, acceptingStates))) {}

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


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

dfa::dfa(dfa::builder& b) : p(move(b.build().p)) {}

dfa&  dfa::operator=(const dfa& 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;


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) {
      #ifdef __EXCEPTIONS
      try {
        row[s] = delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      #else
      size_t r(delta(q, symbol));
      if (r >= SIZE_MAX-1) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      } else {
        row[s] = r;
      }
      #endif
      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) {
      #ifdef __EXCEPTIONS
      try {
        row[s] = getNumberOfStates()+d.delta(q, symbol);
      } catch (std::domain_error e) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      }
      #else
      size_t r(delta(q, symbol));
      if (r >= SIZE_MAX-1) {
        row[s] = getNumberOfStates()+d.getNumberOfStates();
      } else {
        row[s] = r;
      }
      #endif
      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);}


size_t dfa::delta(size_t q, char32_t symbol) const {
  size_t i = distance(
    p->alphabet.begin(),
    find(p->alphabet.begin(), p->alphabet.end(), symbol)
  );
  if (i >= p->alphabet.size()) {
    #ifdef __EXCEPTIONS
    throw std::domain_error(
        string(u8"δ is not defined for symbol ").append(1, symbol)
    );
    #else
    return SIZE_MAX;
    #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))
    );
    #else
    return SIZE_MAX-1;
    #endif
  }
  return p->transitions[q][i];
}

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


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

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


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


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 p->labels.size();
}


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

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

  pImpl() = default;

  pImpl(
      string& initial,
      unordered_set<char32_t>& alphabet,
      unordered_set<string>& acceptingStates,
      unordered_map<string,unordered_map<char32_t,string>>& 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 = string("q").append(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);
    }
  }

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

  static bool valarrayFullTrue(valarray<bool> const& a) {
    bool fullTrue = true;
    for (bool b : a) {
      fullTrue &= b;
    }
    return fullTrue;
  }

  struct ValarrayBoolEqualTo {
    valarray<bool> const& val;

    ValarrayBoolEqualTo(valarray<bool> const& val) : val(val) {}

    bool operator()(valarray<bool> const& other) const {
      return (val.size() == other.size() && valarrayFullTrue(val == other));
    }
  };

  struct ValarrayBoolEqual {
    bool operator()(valarray<bool> const& a, valarray<bool> const& b) const {
      return ValarrayBoolEqualTo(a)(b);
    }
  };
};

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 = 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));
  }
}

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

dfa::builder::builder(builder& 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& dfa::builder::addSymbol(char32_t symbol) {
  p->alphabet.insert(symbol);
  return *this;
}

dfa::builder& dfa::builder::addSymbol(string const& utf8Symbol) {
  return addSymbol(expression::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, expression::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());
  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;
}


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