nfa.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_NFA_H
#define REG_NFA_H

#include <vector>

#include <string>

#include "utils.h"

namespace reg {
class fabuilder;
class dfa;

class nfa {
public:
  struct hash_reference_string_const;
  struct equal_to_reference_string_const ;
  typedef std::unordered_set<
      std::reference_wrapper<std::string const>,
      hash_reference_string_const,
      equal_to_reference_string_const> state_set;
  nfa();
  nfa(
      std::vector<char32_t>&& alphabet,
      std::vector<std::vector<std::valarray<bool>>>&& transitions,
      std::vector<std::string>&& labels,
      std::valarray<bool>&& acceptingStates
    );
  nfa(fabuilder& b);
  nfa(nfa const& n);
  nfa(nfa&& n);
  nfa& operator=(nfa const& n);
  nfa& operator=(nfa&& n);
  virtual ~nfa ();

  operator dfa const&() const;
  bool operator==(nfa const& n) const;
  bool operator!=(nfa const& n) const;
  std::valarray<bool> const& delta(size_t qi, size_t si) const;
  std::valarray<bool> const& delta(size_t qi, std::string const& symbol) const;
  state_set delta(std::string const& q, std::string const& symbol) const;
  std::valarray<bool> const& delta_(size_t qi, char32_t u32symbol) const;
  state_set delta_(std::string const& q, char32_t u32symbol) const;
  std::valarray<bool> deltaHat(size_t qi, std::string const& word) const;
  state_set deltaHat(std::string const& q, std::string const& word) const;
  std::valarray<bool> deltaHat(
      std::valarray<bool> const& qs, std::string const& word) const;
  state_set deltaHat(state_set const& qs, std::string const& word) const;
  std::valarray<bool> deltaHat_(size_t qi, std::u32string const& u32word) const;
  state_set deltaHat_(
      std::string const& q, std::u32string const& u32word) const;
  std::valarray<bool> deltaHat_(
      std::valarray<bool> const& qs, std::u32string const& u32word) const;
  state_set deltaHat_(state_set const& qs, std::u32string const& u32word) const;
  std::valarray<bool> const& epsilonClosure(size_t qi) const;
  state_set epsilonClosure(std::string const& q) const;
  std::valarray<bool> epsilonClosure(std::valarray<bool> const& qs) const;
  state_set epsilonClosure(state_set const& qs) const;
  std::string to_string(std::valarray<bool> const& qs) const;
  std::string to_string(state_set const& qs) const;
  state_set decodeSet(std::valarray<bool> const& qs) const;
  std::valarray<bool> encodeSet(state_set const& qs) const;
  std::string const& getInitialState() const;
  std::vector<std::string> const& getStates() const;
  state_set getStatesSet() const;
  std::valarray<bool> getStatesBools() 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;
  bool isAccepting(std::valarray<bool> const& qs) const;
  bool isAccepting(state_set const& qs) const;
  static fabuilder unite(nfa const& n1, nfa const& n2);
  static fabuilder intersect(nfa const& n1, nfa const& n2);
  static fabuilder subtract(nfa const& n1, nfa const& n2);
  static fabuilder complement(nfa const& n);
  friend std::string findShortestWord(nfa const& n);
  friend std::u32string findShortestWord_(nfa const& n);

  struct hash_reference_string_const {
    inline size_t operator()(
        std::reference_wrapper<std::string const> const& ref) const {
      return std::hash<std::string>()(ref.get());
    }
  };
  struct equal_to_reference_string_const {
    inline bool operator()(
        std::reference_wrapper<std::string const> const& lhs,
        std::reference_wrapper<std::string const> const& rhs) const {
      return &(lhs.get()) == &(rhs.get()) && lhs.get() == rhs.get();
    }
  };
private:
  struct impl;
  std::unique_ptr<impl> pim;
};
std::string findShortestWord(nfa const& n);
std::u32string findShortestWord_(nfa const& n);
} // namespace reg

#endif