非決定性有限オートマトン(NFA)
(automaton/nfa.hpp)

• View this file on GitHub
• Last update: 2025-10-10 17:35:46+09:00
• Include: #include "automaton/nfa.hpp"

概要

NFA $N=(Q,\Sigma,\Delta,s,F)$ は以下を満たすもの．

• 状態集合 $Q$：有限集合
• 文字集合 $\Sigma$：有限集合
• 遷移関数 $\Delta:Q\times\Sigma\to 2^Q$
• 開始状態 $s\in Q$
• 受理状態集合 $F\subseteq Q$

以下のようにして $\Delta:2^Q\times\Sigma\to 2^Q$ とみなす．

• $\forall X\subseteq Q,\forall c\in\Sigma,\Delta(X,c)=\bigcup_{q\in X}\Delta(q,c)$

$\hat{\Delta}:2^Q\times\Sigma^*\to 2^Q$ を以下のように定義する．

• $\forall X\subseteq Q,\hat{\Delta}(X,\epsilon)=X$
• $\forall X\subseteq Q,\forall x\in\Sigma^*,\forall c\in\Sigma,\hat{\Delta}(X,xc)=\Delta(\hat{\Delta}(X,x),c)$

$x\in\Sigma^*$ について，$\hat{\Delta}(s,x)\cap F\neq\emptyset$ ならば $x$ は $N$ によって 受理される，そうでないならば 拒否される という．

言語 $L$ について，任意の文字列 $x$ に対し $x\in L$ と $N$ が $x$ を受理することが同値であるとき，$L$ は $N$ によって受理されるという．

DFA との関係

DFA は自然に NFA とみなせる．

逆に NFA は DFA で再現できる．状態集合を $2^Q$ と思えばよい．

従って DFA と NFA の表現力は等価である．

扱いやすさの面では DFA が，少ない状態数で表すには NFA が便利であるから使い分けが重要．

Depends on

• 決定性有限オートマトン(DFA) (automaton/dfa.hpp)

Code

#pragma once

#include "./dfa.hpp"

template <int c_min = 'a', int c_max = 'z'>
class NFA {
  using t_dfa = DFA<c_min, c_max>;
  using t_nfa = NFA<c_min, c_max>;
  static const int c_size = c_max - c_min + 1;

 public:
  NFA() {}
  NFA(int size_, int start_)
      : _size(size_),
        _start(start_),
        _final(size_, false),
        map(size_, vector(c_size, vector<bool>(size_, false))) {}
  void add(int p, char c, int q) { map[p][c - c_min][q] = true; }
  void remove(int p, char c, int q) { map[p][c - c_min][q] = false; }
  void set_final(int p, bool f) { _final[p] = f; }
  bool get_final(int p) { return _final[p]; }

  t_dfa subset_construction() {
    using T = long long;
    map<T, int> index;
    vector<vector<int>> map1;
    int size1 = 0;
    T start1 = T(1) << _start;
    stack<T> st;
    index[start1] = size1++;
    st.push(start1);
    while (!st.empty()) {
      T x = st.top();
      st.pop();
      vector<int> map_cur(c_size, -1);
      for (int c = 0; c < c_size; c++) {
        T y = 0;
        for (int i = 0; i < _size; i++)
          if ((x >> i) & 1)
            for (int j = 0; j < _size; j++) y |= T(map[i][c][j]) << j;
        if (!index.contains(y)) {
          index[y] = size1++;
          st.push(y);
        }
        map_cur[c] = index[y];
      }
      map1.push_back(map_cur);
    }
    vector<bool> final1(size1, false);
    for (auto [x, i] : index) {
      for (int j = 0; j < _size; j++)
        if (((x >> j) & 1) && _final[j]) final1[i] = 1;
    }
    return t_dfa(index.size(), start1, final1, map1);
  }

 private:
  int _size, _start;
  vector<bool> _final;
  vector<vector<vector<bool>>> map;
};

/**
 * @brief 非決定性有限オートマトン(NFA)
 * @docs docs/automaton/nfa.md
 */

#line 2 "automaton/nfa.hpp"

#line 2 "automaton/dfa.hpp"

template <int c_min = 'a', int c_max = 'z'>
class DFA {
  using t_dfa = DFA<c_min, c_max>;
  static const int c_size = c_max - c_min + 1;

 public:
  DFA() {}
  DFA(int size, int start)
      : _size(size),
        _start(start),
        _final(size, false),
        map(size, vector<int>(c_size, -1)) {}
  DFA(int size, int start, const vector<vector<int>> &map_)
      : _size(size), _start(start), _final(size, false), map(map_) {}
  DFA(int size, int start, const vector<bool> final_,
      const vector<vector<int>> &map_)
      : _size(size), _start(start), _final(final_), map(map_) {}
  void set(int p, char c, int q) { map[p][c - c_min] = q; }
  int get(int p, char c) { return map[p][c - c_min]; }
  void set_final(int p, bool f) { _final[p] = f; }
  bool get_final(int p) { return _final[p]; }

  t_dfa normalize() {
    vector<bool> seen(_size, false);
    vector<int> index(_size, -1);
    vector<int> states;
    queue<int> qu;
    qu.push(_start);
    while (!qu.empty()) {
      int x = qu.front();
      qu.pop();
      seen[x] = true;
      index[x] = states.size();
      states.push_back(x);
      for (int j = 0; j < c_size; j++) {
        int y = map[x][j];
        if (seen[y]) continue;
        seen[y] = true;
        qu.push(y);
      }
    }

    int size1 = states.size();
    vector<bool> final1(size1, false);
    for (int i = 0; i < size1; i++) final1[i] = _final[states[i]];
    vector<vector<int>> map1(size1, vector<int>(c_size, -1));
    for (int i = 0; i < size1; i++)
      for (int j = 0; j < c_size; j++) map1[i][j] = index[map[states[i]][j]];
    return t_dfa(size1, index[_start], final1, map1);
  }

  t_dfa minimize() {
    vector<int> partition(_size, -1);
    {
      int accept = -1, reject = -1;
      for (int i = 0; i < _size; i++)
        if (_final[i])
          partition[i] = accept == -1 ? (accept = i) : accept;
        else
          partition[i] = reject == -1 ? (reject = i) : reject;
    }

    vector<int> partition_new(_size, -1);
    while (true) {
      fill(partition_new.begin(), partition_new.end(), -1);
      for (int i = 0; i < _size; i++) {
        if (partition_new[i] != -1) continue;
        partition_new[i] = i;
        for (int j = i + 1; j < _size; j++)
          if (partition[i] == partition[j] && equivalent(i, j, partition))
            partition_new[j] = i;
      }
      if (partition == partition_new) break;
      swap(partition, partition_new);
    }

    int size1 = 0;
    vector<int> index(_size, -1), leader;
    vector<bool> final1;
    for (int i = 0; i < _size; i++)
      if (partition[i] == i) {
        index[i] = size1++;
        leader.push_back(i);
        final1.push_back(_final[i]);
      } else {
        index[i] = index[partition[i]];
      }
    vector<vector<int>> map1(size1, vector<int>(c_size, -1));
    for (int i = 0; i < size1; i++)
      for (int j = 0; j < c_size; j++) map1[i][j] = index[map[leader[i]][j]];
    return t_dfa(size1, index[_start], final1, map1).normalize();
  }

  bool operator==(const t_dfa &d) const {
    if (_size != d._size) return false;
    if (_start != d._start) return false;
    if (_final != d._final) return false;
    return map == d.map;
  }
  int size() { return _size; }
  int start() { return _start; }

 private:
  int _size, _start;
  vector<bool> _final;
  vector<vector<int>> map;

  bool equivalent(int i, int j, const vector<int> &partition) {
    if (i == j) return true;
    for (int k = 0; k < c_size; k++)
      if (partition[map[i][k]] != partition[map[j][k]]) return false;
    return true;
  }
};

/**
 * @brief 決定性有限オートマトン(DFA)
 * @docs docs/automaton/dfa.md
 */
#line 4 "automaton/nfa.hpp"

template <int c_min = 'a', int c_max = 'z'>
class NFA {
  using t_dfa = DFA<c_min, c_max>;
  using t_nfa = NFA<c_min, c_max>;
  static const int c_size = c_max - c_min + 1;

 public:
  NFA() {}
  NFA(int size_, int start_)
      : _size(size_),
        _start(start_),
        _final(size_, false),
        map(size_, vector(c_size, vector<bool>(size_, false))) {}
  void add(int p, char c, int q) { map[p][c - c_min][q] = true; }
  void remove(int p, char c, int q) { map[p][c - c_min][q] = false; }
  void set_final(int p, bool f) { _final[p] = f; }
  bool get_final(int p) { return _final[p]; }

  t_dfa subset_construction() {
    using T = long long;
    map<T, int> index;
    vector<vector<int>> map1;
    int size1 = 0;
    T start1 = T(1) << _start;
    stack<T> st;
    index[start1] = size1++;
    st.push(start1);
    while (!st.empty()) {
      T x = st.top();
      st.pop();
      vector<int> map_cur(c_size, -1);
      for (int c = 0; c < c_size; c++) {
        T y = 0;
        for (int i = 0; i < _size; i++)
          if ((x >> i) & 1)
            for (int j = 0; j < _size; j++) y |= T(map[i][c][j]) << j;
        if (!index.contains(y)) {
          index[y] = size1++;
          st.push(y);
        }
        map_cur[c] = index[y];
      }
      map1.push_back(map_cur);
    }
    vector<bool> final1(size1, false);
    for (auto [x, i] : index) {
      for (int j = 0; j < _size; j++)
        if (((x >> j) & 1) && _final[j]) final1[i] = 1;
    }
    return t_dfa(index.size(), start1, final1, map1);
  }

 private:
  int _size, _start;
  vector<bool> _final;
  vector<vector<vector<bool>>> map;
};

/**
 * @brief 非決定性有限オートマトン(NFA)
 * @docs docs/automaton/nfa.md
 */

Back to top page