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

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

概要

DFA $M=(Q,\Sigma,\delta,s,F)$ は以下を満たすもの．

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

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

$\forall q\in Q,\hat{\delta}(q,\epsilon)=q$
$\forall q\in Q,\forall x\in\Sigma^*,\forall c\in \Sigma,\hat{\delta}(q,xc)=\delta(\hat{\delta}(q,x),c)$

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

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

自身を受理する DFA が存在する言語を正規言語と呼ぶ．

利用

状態集合 $Q$，文字集合 $\Sigma$ の DFA $M$ が与えられたとする．

このとき例えば $M$ によって受理される長さ $N$ 以下の文字列の総数を $O(2^{\lvert Q \rvert}\lvert \Sigma \rvert N)$ 時間で計算できる．

単純に bit dp すればよい．

遷移に重みがついているような場合でも問題ない．

Myhill-Nerode の定理

言語 $L$ に対し，$\Sigma^*$ 上の同値関係 $\sim_L$ を以下で定める．

\[x \sim_L y \iff \forall z\in\Sigma^*(xz\in L\iff yz\in L)\]

Myhill-Nerode の定理の主張は以下の通り．

$L$ が正規言語であることと $\sim_L$ の同値類が有限個であることは同値．
$L$ が正規言語のとき，$L$ を受理する DFA の状態数の最小値は $\sim_L$ の同値類の個数に一致する．
$L$ が正規言語のとき，$L$ を受理する状態数最小の DFA は一意．

DFA の推定

規則的に定義された言語の場合，深い考察をせずに DFA が構築できる場合がある．

例題：ABC418-G

短い文字数では正しく判定できるような DFA を作る．
DFA $M$ が$L$ を受理するならば $f(M)$ と $M$ が同型になるような変換 $f$ を用意し，実際に同型になったら終了．

Required by

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

Code

#pragma once

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

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

概要

利用

Myhill-Nerode の定理

DFA の推定

Required by

Code

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