dfa.h

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/>.

#ifndef REG_DFA_H
#define REG_DFA_H

#include <memory>

#include <vector>

#include <string>

#include <valarray>

namespace reg {
class fabuilder;
class nfa;

class dfa {
 public:
  dfa();
  dfa(std::vector<char32_t>&& alphabet,
      std::vector<std::vector<size_t>>&& transitions,
      std::vector<std::string>&& labels, std::valarray<bool>&& acceptingStates);
  dfa(fabuilder& b, bool force = false);
  dfa(dfa const& d);
  dfa(dfa&& d);
  dfa& operator=(dfa const& d);
  dfa& operator=(dfa&& d);
  virtual ~dfa();

  operator nfa const&() const;
  bool operator==(dfa const& d) const;
  bool operator!=(dfa const& d) const;
  bool operator==(nfa const& d) const;
  bool operator!=(nfa const& d) const;
  size_t delta(size_t qi, size_t si) const;
  size_t delta(size_t qi, std::string const& symbol) const;
  std::string const& delta(std::string const& q,
                           std::string const& symbol) const;
  size_t delta_(size_t qi, char32_t u32symbol) const;
  std::string const& delta_(std::string const& q, char32_t u32symbol) const;
  size_t deltaHat(size_t qi, std::string const& word) const;
  std::string const& deltaHat(std::string const& q,
                              std::string const& word) const;
  size_t deltaHat_(size_t qi, std::u32string const& u32word) const;
  std::string const& deltaHat_(std::string const& q,
                               std::u32string const& u32word) const;
  std::string const& getInitialState() const;
  std::vector<std::string> const& getStates() const;
  std::vector<std::string> const& getAlphabet() const;
  std::vector<char32_t> const& getAlphabet_() const;
  bool isAccepting(size_t qi) const;
  bool isAccepting(std::string const& q) const;
  static fabuilder unite(dfa const& d1, dfa const& d2);
  static fabuilder intersect(dfa const& d1, dfa const& d2);
  static fabuilder subtract(dfa const& d1, dfa const& d2);
  static fabuilder complement(dfa const& d);

  static std::vector<std::valarray<bool>> indistinguishableStates(
      std::vector<std::vector<size_t>> const& transitions,
      std::valarray<bool> const& accepting);

  friend std::string findShortestWord(dfa const& d);
  friend std::u32string findShortestWord_(dfa const& d);

 private:
  struct impl;
  std::unique_ptr<impl> pim;
};
std::string findShortestWord(dfa const& d);
std::u32string findShortestWord_(dfa const& d);
}  // namespace reg

#endif