dfa.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 "dfa.h"
using std::make_unique;
using std::string;
using std::to_string;
using std::u32string;
using std::valarray;
using std::vector;

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::none_of;

#include <cstdint>

#include "fabuilder.h"
#include "nfa.h"
#include "utils.h"

namespace reg {

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

  impl()
      : accepting(false, 1),
        u32alphabet(0),
        alphabet(0),
        labels(1),
        transitions(1) {}

  impl(vector<char32_t>&& u32alphabet, vector<vector<size_t>>&& transitions,
       vector<string>&& labels, valarray<bool>&& accepting)
      : accepting(move(accepting)),
        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(symbol));
    }
  }
};

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

dfa::dfa(fabuilder& b, bool force) : dfa(b.buildDfa(force)) {}

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

dfa::dfa(dfa const& d) : pim(new impl(*(d.pim))) {}


dfa::dfa(dfa&& d) : pim(new impl) { pim.swap(d.pim); }

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


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

dfa::~dfa() = default;

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


bool dfa::operator==(dfa const& d) const {
  forward_list<char32_t> unitedAlphabet(getAlphabet_().begin(),
                                        getAlphabet_().end());
  size_t unitedAlphabetSize(getAlphabet_().size());
  for (char32_t symbol : d.getAlphabet_()) {
    if (index_of(getAlphabet_(), symbol) == getAlphabet_().size()) {
      unitedAlphabet.push_front(symbol);
      unitedAlphabetSize++;
    }
  }
  vector<vector<size_t>> tTable(getStates().size() + d.getStates().size() + 1,
                                vector<size_t>(unitedAlphabetSize));
  valarray<bool> accepting(false,
                           getStates().size() + d.getStates().size() + 1);
  for (size_t q(0); q < getStates().size(); q++) {
    size_t s(0);
    vector<size_t>& row = tTable[q];
    for (char32_t symbol : unitedAlphabet) {
      try {
        row[s] = delta_(q, symbol);
      } catch (symbol_not_found e) {
        row[s] = getStates().size() + d.getStates().size();
      }
      s++;
    }
    accepting[q] = isAccepting(q);
  }
  for (size_t q(0); q < d.getStates().size(); q++) {
    size_t s(0);
    vector<size_t>& row = tTable[q + getStates().size()];
    for (char32_t symbol : unitedAlphabet) {
      try {
        row[s] = getStates().size() + d.delta_(q, symbol);
      } catch (symbol_not_found e) {
        row[s] = getStates().size() + d.getStates().size();
      }
      s++;
    }
    accepting[q + getStates().size()] = d.isAccepting(q);
  }
  for (size_t s(0); s < unitedAlphabetSize; s++) {
    tTable[getStates().size() + d.getStates().size()][s] =
        getStates().size() + d.getStates().size();
  }
  return indistinguishableStates(tTable, accepting)[0][getStates().size()];
}

bool dfa::operator!=(dfa const& d) const { return !operator==(d); }

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

bool dfa::operator!=(nfa const& n) const { return !operator==(n); }


size_t dfa::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];
}


size_t dfa::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);
  }
}


size_t dfa::delta(size_t qi, string const& symbol) const {
  return delta_(qi, converter.from_bytes(symbol)[0]);
}


string const& dfa::delta_(string const& q, char32_t u32symbol) const {
  try {
    return getStates()[delta_(index_of(getStates(), q), u32symbol)];
  } catch (state_not_found e) {
    throw state_not_found(q);
  }
}


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


size_t dfa::deltaHat_(size_t qi, u32string const& u32word) const {
  for (char32_t symbol : u32word) {
    qi = delta_(qi, symbol);
  }
  return qi;
}


size_t dfa::deltaHat(size_t qi, string const& word) const {
  return deltaHat_(qi, converter.from_bytes(word));
}


string const& dfa::deltaHat_(string const& q, u32string const& u32word) const {
  return pim->labels[deltaHat_(index_of(getStates(), q), u32word)];
}


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


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


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


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


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


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


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


u32string findShortestWord_(dfa const& d) {
  auto const& pim = d.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 : d.getAlphabet_()) {
        size_t reached = d.delta_(stateWord.first, symbol);
        u32string shWord = stateWord.second + symbol;
        if (pim->accepting[reached]) {
          return shWord;
        }
        if (!shortestWords.count(reached)) {
          shortestWords.emplace(reached, move(shWord));
        }
      }
    }
  }
  throw std::logic_error("This DFA doesn't accept any words!");
}


string findShortestWord(dfa const& d) {
  return converter.to_bytes(findShortestWord_(d));
}


fabuilder dfa::unite(dfa const& d1, dfa const& d2) {
  return fabuilder(d1).unite(d2);
}


fabuilder dfa::intersect(dfa const& d1, dfa const& d2) {
  return fabuilder(d1).intersect(d2);
}


fabuilder dfa::subtract(dfa const& d1, dfa const& d2) {
  fabuilder b1(d1);
  for (auto symbol : d2.getAlphabet_()) {
    b1.addSymbol_(symbol);
  }
  return b1.complement().unite(d2).complement();
}


fabuilder dfa::complement(dfa const& d) { return fabuilder(d).complement(); }


vector<valarray<bool>> dfa::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;
}

}  // namespace reg