nfa.cpp

Go to the documentation of this file.

#include "nfa.h"
using std::valarray;
using std::vector;
using std::string;
using std::unique_ptr;
using std::shared_ptr;
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;
using std::sort;

#include <iterator>
using std::distance;

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

namespace reg {

struct nfa::pImpl {
  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(expression::converter->to_bytes(symbol));
      }
    }
    epsClosures = vector<valarray<bool>>(pImpl::labels.size());
  }


  dfa const& getEquivalentDfa(nfa const* owner) {
    if (!equivalent) {
      equivalent.reset(new dfa::dfa(dfa::builder(*owner).purge().merge()));
    }
    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 = 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)
    );
    #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, expression::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, expression::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, expression::converter->from_bytes(utf8Word));
}


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> 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];
}

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


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

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;

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

  pImpl() = default;

  pImpl(
      string& initial,
      unordered_set<string>& acceptingStates,
      unordered_set<char32_t>& alphabet,
      unordered_map<string,unordered_map<char32_t,unordered_set<string>>>& 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());
  unordered_map<string,unordered_map<char32_t,unordered_set<string>>> 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)));
    }
  }
  p = unique_ptr<pImpl>(new pImpl(initial, acceptingStates, alphabet, transitions));
}

nfa::builder::builder(builder& 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(expression::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, expression::converter->from_bytes(utf8Symbol)[0]);
}


nfa nfa::builder::build() {
  p->alphabet.insert(U'\0');
  vector<char32_t> alphabetV(p->alphabet.begin(), p->alphabet.end());
  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