nfa.h

Go to the documentation of this file.

#ifndef REG_NFA_H
#define REG_NFA_H

#include <memory>

#include <vector>

#include <valarray>

#include <string>

namespace reg {
class dfa;

class nfa {
public:
  class builder;
  nfa();
  nfa(nfa const& n);
  nfa(nfa&& n);
  nfa(dfa const& d);
  nfa(builder& b);
  nfa& operator=(nfa const& n);
  nfa& operator=(nfa&& n);
  virtual ~nfa ();

  bool operator==(nfa const& n) const;
  bool operator!=(nfa const& n) const;
  std::valarray<bool> const& delta(size_t q, char32_t symbol) const;
  std::valarray<bool> const& delta(size_t q, std::string const& utf8Symbol) const;
  std::valarray<bool> deltaHat(size_t q, std::u32string const& word) const;
  std::valarray<bool> deltaHat(size_t q, std::string const& utf8Word) const;
  std::valarray<bool> deltaHat(std::valarray<bool> const& qs, std::u32string const& word) const;
  std::valarray<bool> deltaHat(std::valarray<bool> const& qs, std::string const& utf8Word) const;
  std::valarray<bool> const& epsilonClosure(size_t q) const;
  std::valarray<bool> epsilonClosure(std::valarray<bool> const& qs) const;
  std::u32string getShortestWord() const;
  std::string getShortestUtf8Word() const;
  std::string const& getLabelOf(size_t q) const;
  std::string getLabelOf(std::valarray<bool> const& qs) const;
  std::vector<char32_t> const& getAlphabet() const;
  std::vector<std::string> const& getUtf8Alphabet() const;
  size_t getNumberOfStates() const;
  bool isAccepting(size_t q) const;
  bool hasAccepting(std::valarray<bool> const& qs) const;
  static nfa::builder unite(nfa const& n1, nfa const& n2);
  static nfa::builder intersect(nfa const& n1, nfa const& n2);
  static nfa::builder subtract(nfa const& n1, nfa const& n2);
  static nfa::builder complement(nfa const& n);

  class builder {
  public:
    builder();
    builder(nfa const& nfa);
    builder(dfa const& dfa);
    builder(builder const& b);
    builder(builder&& b);
    builder& operator=(builder const& b);
    builder& operator=(builder&& b);
    virtual ~builder ();

    builder& addSymbol(char32_t symbol);
    builder& addSymbol(std::string const& utf8Symbol);
    builder& setAccepting(std::string const& state, bool accept);
    builder& makeInitial(std::string const& state);
    builder& addTransition(std::string const& from, std::string const& to, char32_t symbol);
    builder& addTransition(std::string const& from, std::string const& to, std::string const& utf8Symbol);
    builder& unite(nfa const& other);
    builder& intersect(nfa const& other);
    builder& normalizeStateNames(std::string const& prefix);
    nfa build();
  private:
    struct pImpl;
    std::unique_ptr<pImpl> p;
  };
private:
  struct pImpl;
  std::unique_ptr<pImpl> p;
  nfa(
      std::vector<char32_t>& alphabet,
      std::vector<std::vector<std::valarray<bool>>>& transitions,
      std::vector<std::string>& labels,
      std::valarray<bool>& acceptingStates
    );
};
} // namespace reg
#endif