nfa.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 "nfa.h"
using std::make_pair;
using std::make_unique;
using std::reference_wrapper;
using std::string;
using std::u32string;
using std::unordered_set;
using std::valarray;
using std::vector;

using std::move;

#include <unordered_map>
using std::unordered_map;

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

#include <iterator>

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

namespace reg {

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

  impl()
      : equivalent(),
        accepting(false, 1),
        u32alphabet(1, U'\0'),
        alphabet(1, ""),
        epsClosures(1),
        labels(1),
        transitions(1, vector<valarray<bool>>(1, valarray<bool>(false, 1))) {}

  impl(vector<char32_t>&& u32alphabet,
       vector<vector<valarray<bool>>>&& transitions, vector<string>&& labels,
       valarray<bool>&& acceptingStates)
      : accepting(move(acceptingStates)),
        u32alphabet(move(u32alphabet)),
        labels(move(labels)),
        transitions(move(transitions)) {
    alphabet.reserve(this->u32alphabet.size());
    for (char32_t symbol : this->u32alphabet) {
      alphabet.push_back(converter.to_bytes(u32string(!!symbol, symbol)));
    }
    epsClosures = vector<valarray<bool>>(this->labels.size());
  }
};

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

nfa::nfa(fabuilder& b) : nfa(b.buildNfa()) {}

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

#ifndef DOXYGEN_SHOULD_SKIP_THIS
nfa::operator dfa const&() const {
  if (!pim->equivalent) {
    pim->equivalent = std::make_shared<dfa const>(
        fabuilder(*this).minimize(true).normalizeStateNames("").buildDfa());
  }
  return *pim->equivalent;
}
#endif  // DOXYGEN_SHOULD_SKIP_THIS


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


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


valarray<bool> const& nfa::delta(size_t qi, size_t si) const {
  if (si >= pim->alphabet.size()) {
    throw symbol_not_found(si);
  }
  if (qi >= pim->labels.size()) {
    throw state_not_found(qi);
  }
  return pim->transitions[qi][si];
}


valarray<bool> const& nfa::delta_(size_t qi, char32_t u32symbol) const {
  try {
    return delta(qi, index_of(getAlphabet_(), u32symbol));
  } catch (symbol_not_found e) {
    throw symbol_not_found(u32symbol);
  }
}


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


nfa::state_set nfa::delta_(string const& q, char32_t u32symbol) const {
  try {
    return decodeSet(delta_(index_of(getStates(), q), u32symbol));
  } catch (state_not_found e) {
    throw state_not_found(q);
  }
}


nfa::state_set nfa::delta(string const& q, string const& symbol) const {
  return delta_(q, converter.from_bytes(symbol)[0]);
}


valarray<bool> nfa::deltaHat_(size_t qi, u32string const& u32word) const {
  if (qi >= pim->labels.size()) {
    throw state_not_found(qi);
  }
  valarray<bool> qs(pim->labels.size());
  qs[qi] = true;
  return deltaHat_(qs, u32word);
}


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


nfa::state_set nfa::deltaHat_(string const& q, u32string const& u32word) const {
  try {
    return decodeSet(deltaHat_(index_of(getStates(), q), u32word));
  } catch (state_not_found e) {
    throw state_not_found(q);
  }
}


nfa::state_set nfa::deltaHat(string const& q, string const& word) const {
  return deltaHat_(q, converter.from_bytes(word));
}


valarray<bool> nfa::deltaHat_(valarray<bool> const& qs,
                              u32string const& u32word) const {
  valarray<bool> ps = epsilonClosure(qs);
  for (char32_t symbol : u32word) {
    valarray<bool> reached(pim->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& word) const {
  return deltaHat_(qs, converter.from_bytes(word));
}


nfa::state_set nfa::deltaHat_(nfa::state_set const& qs,
                              u32string const& u32word) const {
  return decodeSet(deltaHat_(encodeSet(qs), u32word));
}


nfa::state_set nfa::deltaHat(nfa::state_set const& qs,
                             string const& word) const {
  return deltaHat_(qs, converter.from_bytes(word));
}


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


nfa::state_set nfa::epsilonClosure(string const& q) const {
  try {
    return decodeSet(epsilonClosure(index_of(getStates(), q)));
  } catch (state_not_found e) {
    throw state_not_found(q);
  }
}


valarray<bool> nfa::epsilonClosure(valarray<bool> const& qs) const {
  valarray<bool> closure(pim->labels.size());
  size_t range = min(qs.size(), getStates().size());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      closure |= epsilonClosure(q);
    }
  }
  return closure;
}


nfa::state_set nfa::epsilonClosure(nfa::state_set const& qs) const {
  return decodeSet(epsilonClosure(encodeSet(qs)));
}


string nfa::to_string(valarray<bool> const& qs) const {
  string label;
  size_t range = min(qs.size(), getStates().size());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      label = label.append(1, label.length() == 0 ? '{' : ',');
      // label = label.append(1, '{' - !!label.length() * ('{' - ','));
      label = label.append(getStates()[q]);
    }
  }
  if (label.length() == 0) {
    return string("{}");
  } else {
    return label.append(1, '}');
  }
}


string nfa::to_string(nfa::state_set const& qs) const {
  return to_string(encodeSet(qs));
}


nfa::state_set nfa::decodeSet(valarray<bool> const& qs) const {
  nfa::state_set states;
  states.reserve(getStates().size());
  size_t range = min(qs.size(), getStates().size());
  for (size_t q = 0; q < range; q++) {
    if (qs[q]) {
      states.emplace(getStates()[q]);
    }
  }
  return states;
}


valarray<bool> nfa::encodeSet(nfa::state_set const& qs) const {
  valarray<bool> states(getStates().size());
  for (size_t qi = 0; qi < getStates().size(); qi++) {
    states[qi] = qs.count(getStates()[qi]);
  }
  return states;
}


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


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


nfa::state_set nfa::getStatesSet() const {
  return nfa::state_set(getStates().begin(), getStates().end());
}


valarray<bool> nfa::getStatesBools() const {
  return valarray<bool>(true, getStates().size());
}


vector<char32_t> const& nfa::getAlphabet_() const { return pim->u32alphabet; }


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


bool nfa::isAccepting(size_t qi) const {
  if (qi >= pim->labels.size()) {
    throw state_not_found(qi);
  }
  return pim->accepting[qi];
}


bool nfa::isAccepting(string const& q) const {
  try {
    return isAccepting(index_of(getStates(), q));
  } catch (state_not_found e) {
    throw state_not_found(q);
  }
}


bool nfa::isAccepting(valarray<bool> const& qs) const {
  size_t range = min(qs.size(), getStates().size());
  for (size_t q = 0; q < range; q++) {
    if (qs[q] && pim->accepting[q]) {
      return true;
    }
  }
  return false;
}


bool nfa::isAccepting(nfa::state_set const& qs) const {
  for (size_t qi = 0; qi < getStates().size(); qi++) {
    if (pim->accepting[qi] && qs.count(getStates()[qi])) {
      return true;
    }
  }
  return false;
}


u32string findShortestWord_(nfa const& n) {
  auto const& pim = n.pim;
  if (pim->accepting[0]) {
    return U"";
  }
  unordered_map<size_t, u32string> shortestWords(pim->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 : n.getAlphabet_()) {
        valarray<bool> reached =
            n.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 (pim->accepting[q]) {
              return shWord;
            }
            if (!shortestWords.count(q)) {
              shortestWords.emplace(q, shWord);
            }
          }
        }
      }
    }
  }
  throw std::logic_error("This NFA doesn't accept any words!");
}

string findShortestWord(nfa const& n) {
  return converter.to_bytes(findShortestWord_(n));
}


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


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


fabuilder nfa::subtract(nfa const& n1, nfa const& n2) {
  fabuilder b2(n2);
  for (auto symbol : n1.getAlphabet_()) {
    b2.addSymbol_(symbol);
  }
  b2.complement(true).minimize();
  return fabuilder(n1).intersect(b2.buildNfa());
}


fabuilder nfa::complement(nfa const& n) {
  return fabuilder(n).complement(true).minimize();
}

nfa::nfa(nfa const& n) : pim(new impl(*(n.pim))) {}


nfa::nfa(nfa&& n) : pim(new impl) { pim.swap(n.pim); }

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


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

nfa::~nfa() = default;

}  // namespace reg