有限オートマトン

有限オートマトン(finite automaton)とは正規言語を受理する計算モデルである。

以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。

$\global\def\mathderiv{\mathrel{\mathop{\Rightarrow}}^{*}}$ $\global\def\mathgen{\rightsquigarrow}$ $\global\def\emptyword{\varepsilon}$ $\global\def\kleenecl#1{{#1}^{*}}$ $\global\def\interpret#1{[\![#1]\!]}$ $\global\def\mathautomaton#1{\mathcal{#1}}$ $\global\def\mathnat{\mathbb{N}}$ $\global\def\qed{\blacksquare}$

有限オートマトンの導入

この節では有限オートマトンやその周辺の重要な諸概念を定義する。

有限オートマトンの定義

有限オートマトン(finite automaton)とは

  1. 状態集合(a set of states)と呼ばれる有限集合 $Q$
  2. 記号集合 $\Sigma$
  3. 遷移関係(transition relation)と呼ばれる集合 $\Delta \subseteq Q\times (\Sigma \cup \{\emptyword\}) \times Q$
  4. 開始状態(initial state)と呼ばれる $q_{I}\in Q$
  5. 受理状態(accepting state)最終状態(final state)と呼ばれる集合 $F\subseteq Q$

の5つ組 $(Q, \Sigma, \Delta, q_{I}, F)$ である。

決定性有限オートマトンと非決定性有限オートマトン

有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が次の2条件を満たすとき、$\mathautomaton{A}$ は決定性有限オートマトン(deterministic finite automaton)であると言う。

  1. $(q, a, q')\in \Delta$ に対して $a=\emptyword$ ならば、$q=q'$
  2. 各 $(q, a) \in Q\times \Sigma$ という組に対して、$(q, a, q')\in \Delta$ という形の元は高々一個

有限オートマトン $\mathautomaton{A}$ が決定性有限オートマトンとは限らないことを明示したいときに、 $\mathautomaton{A}$ は非決定性有限オートマトン(nondeterministic finite automaton)であると言うことがある。

有限オートマトンの受理する言語

有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ と 記号列 $w \in \kleenecl{\Sigma}$ について、 次の2条件を満たす状態の列 $q_{0}, q_{1}, \dots, q_{n}$ を 記号列 $w$ による $q_{0}$ から $q_{n}$ への $\mathautomaton{A}$ の状態遷移と言う。

  1. $w=a_{1}a_{2} \dots a_{n}$ (ただし、各 $i=1, \dots, n$ について $a_{i}\in \Sigma\cup\{\emptyword\}$)
  2. すべての $i\in \{1, \dots n\}$ について $(q_{i-1}, a_{i}, q_{i})\in \Delta$

記号列 $w$ による $\mathautomaton{A}$ の状態遷移 $q_{0}, q_{1}, \dots, q_{n}$ であって $q_{0} = q_{I}$, $q_{n}\in F$ を満たすものが存在するとき、 「有限オートマトン $\mathautomaton{A}$ が 記号列 $w$ を受理する」と言う。

有限オートマトン $\mathautomaton{A}$ が受理する 記号列全体のことを 有限オートマトン $\mathautomaton{A}$ の受理する言語 と言い、$L(\mathautomaton{A})$ と書く。

有限オートマトンの等価性

有限オートマトン $\mathautomaton{A}$ と 有限オートマトン $\mathautomaton{A'}$ が等価であるとは, $L(\mathautomaton{A})=L(\mathautomaton{A'})$ を満たすことである.

有限オートマトンの例

この節では有限オートマトンの例を紹介する。

$0$ と $1$ からなる有限記号列全体を受理する有限オートマトン

$$Q=\{q_{I}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{I}), (q_{I}, 1, q_{I})\}$$ $$F= \{q_{I}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。また、$\mathautomaton{A}$ は決定性有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ は $0$ と $1$ からなる有限記号列をすべて受理する。

$0$ と $1$ のみを受理する有限オートマトン

$$Q=\{q_{I}, q_{1}, q_{2}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{1}), (q_{I}, 1, q_{1}), (q_{1}, 0, q_{2}), (q_{1}, 1, q_{2})\}$$ $$F= \{q_{1}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ は $0$ と $1$ のみを受理する。

$0$ と $1$ からなる有限記号列のうち、$1$ をちょうど3個含む記号列全体を受理する有限オートマトン

$$Q=\{q_{I}, q_{1}, q_{2}, q_{3}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{I}), (q_{I}, 1, q_{1}), (q_{1}, 0, q_{1}), (q_{1}, 1, q_{2}), (q_{2}, 0, q_{2}), (q_{2}, 1, q_{3}), (q_{3}, 0, q_{3})\}$$ $$F= \{q_{3}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ は $0$ と $1$ からなる有限記号列のうち、$1$ をちょうど3個含む記号列のみを受理する。

$0$ と $1$ からなる有限記号列のうち、$1$ を高々3個含む記号列全体を受理する有限オートマトン その1

$$Q=\{q_{I}, q_{1}, q_{2}, q_{3}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{I}), (q_{I}, 1, q_{1}), (q_{1}, 0, q_{1}), (q_{1}, 1, q_{2}), (q_{2}, 0, q_{2}), (q_{2}, 1, q_{3}), (q_{3}, 0, q_{3}), (q_{I}, \emptyword, q_{3}), (q_{1}, \emptyword, q_{3}), (q_{2}, \emptyword, q_{3})\}$$ $$F= \{q_{3}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ は $0$ と $1$ からなる有限記号列のうち、$1$ を高々3個含む記号列のみを受理する。

$0$ と $1$ からなる有限記号列のうち、$1$ を高々3個含む記号列全体を受理する有限オートマトン その2

$$Q=\{q_{I}, q_{1}, q_{2}, q_{3}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{I}), (q_{I}, 0, q_{1}), (q_{I}, 0, q_{2}), (q_{I}, 0, q_{3}), (q_{I}, 1, q_{1}), (q_{1}, 0, q_{1}), (q_{1}, 1, q_{2}), (q_{2}, 0, q_{2}), (q_{2}, 1, q_{3}), (q_{3}, 0, q_{3}), (q_{I}, \emptyword, q_{3})\}$$ $$F= \{q_{3}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ も $0$ と $1$ からなる有限記号列のうち、$1$ を高々3個含む記号列のみを受理する。

自然数の二進表現全体を受理する有限オートマトン

$$Q=\{q_{I}, q_{1}, q_{2}\}$$ $$\Sigma=\{0, 1\}$$ $$\Delta=\{(q_{I}, 0, q_{2}), (q_{I}, 1, q_{1}), (q_{1}, 0, q_{1}), (q_{1}, 1, q_{1})\}$$ $$F= \{q_{1}, q_{2}\}$$

とすると、$\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ は有限オートマトンである。

この有限オートマトン $\mathautomaton{A}$ は 自然数の二進表現のみを受理する。

正規言語、正規表現との関係

この節では有限オートマトン、正規言語および正規表現の関係を述べる。

定理 1

言語 $L$ について以下は同値である.

  1. $L$ は正規言語である。
  2. $L=\interpret{\alpha}$ なる正規表現 $\alpha$ が存在する。
  3. $L$ を受理する有限オートマトンが存在する。

この定理の証明は、項目正規言語を参照せよ。

反復補題(ポンピング補題)

この節では反復補題(pumping lemma)について述べる*1。 反復補題はポンピング補題ポンプ補題と呼ばれることもある。

反復補題はある記号列の集合が正規言語ではない証明などに よく用いられる。

補題 2 反復補題(pumping lemma)

状態集合の大きさが $n$ の有限オートマトン $\mathautomaton{A}$ に記号列 $w$ が受理されるとする。

$\left|w\right|>n$ であるとき、次の四条件を満たす記号列 $x$, $y$, $z$ が存在する。

  1. $w=xyz$。
  2. $\left|y\right|>0$。
  3. 任意の$m\in\mathnat$に対して、記号列 $xy^{m}z$ は$\mathautomaton{A}$ に受理される。
  4. $|xy|\leq n$。

反復補題の証明

有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ に $w$ が受理されるとする。 以下 $n:=\left|Q\right|$, $l:=\left|w\right|$, $l>n$ とする。

有限オートマトン $\mathautomaton{A}$ に $w$ が受理されることから、

  1. $w=a_{1}a_{2} \dots a_{k}$ (ただし、各 $i=1, \dots, k$ について $a_{i}\in \Sigma\cup\{\emptyword\}$)。
  2. すべての $i\in \{1, \dots k\}$ について $(q_{i-1}, a_{i}, q_{i})\in \Delta$。
  3. $q_{0}=q_{I}$, $q_{k}\in F$。

を満たす状態の列 $q_{0}, q_{1}, \dots, q_{k}$ と記号の列 $a_{1}, a_{2}, \dots, a_{k}$が存在する (ただし、$k\geq l$)。

$l>n$ から長さが $n$ の $w$ の接頭語 $w_{0}$ が存在する。 すると、$q_{0}, q_{1}, \dots, q_{k}$ の部分列であって、$w_{0}$ による $\mathautomaton{A}$ の状態遷移 $$q_{0}, q_{1}, \dots, q_{k_{0}}$$ が存在する(ただし $n\leq k_{0}\leq k$)。

すると、鳩ノ巣原理より

  1. $(q_{i-1}, a_{i}, q_{i})$, $(q_{i+j-1}, a_{i+j}, q_{i+j})\in \Delta$ (ただし、$a_{i}\neq\emptyword$, $a_{i+j}\neq\emptyword$)
  2. $q_{i}=q_{i+j}$

という条件を満たす自然数の組 $(i, j)$ (ただし $0\leq i\leq k_{0}$, $0< j\leq k_{0}$)が少なくとも1つ存在する。 以下その $i$, $j$ を固定する。

$$x:=a_{1}a_{2}\ldots a_{i}, $$ $$y:=a_{i+1}a_{i+2}\ldots a_{i+j}, $$ $$z:=a_{i+j+1}a_{i+j+2}\ldots a_{k}, $$ とすると、$w=xyz$ である。また、$a_{i+j}\neq\emptyword$ であるから $\left|y\right|>0$。 さらに、定義より $xy$ は $w_{0}$ の部分列であるから、$|xy|\leq n$。

任意の$m\in\mathnat$に対して,記号列 $xy^{m}z$ が $\mathautomaton{A}$ に受理されることを示す。

以下,記号列 $x$, $y$, $z$ による $\mathautomaton{A}$ の状態遷移をそれぞれ $$Q_{x}=q_{0}, \dots, q_{i};$$ $$Q_{y}=q_{i+1}, \dots, q_{i+j};$$ $$Q_{z}=q_{i+j+1}, \dots, q_{k};$$ と書くことにする。

$m=0$ のときを示す。

$q_{i}=q_{i+j}$ に注意すると、$(q_{i}, a_{i+j+1}, q_{i+j+1})\in \Delta$ である。 よって、 $$Q_{x}Q_{z}=q_{0}, \dots, q_{i}, q_{i+j+1}, \dots, q_{k}$$ は記号列 $xz$ による $\mathautomaton{A}$ の状態遷移である。 $q_{0}=q_{I}$, $q_{k}\in F$ であるから、$xz$($=xy^{0}z$) は $\mathautomaton{A}$ に受理される。

$m>0$ のときを示す。

$q_{i}=q_{i+j}$ に注意すると、$(q_{i+j}, a_{i+j+1}, q_{i+1})\in \Delta$ である。 $$Q_{x}\overbrace{Q_{y}\dots Q_{y}}^{m\text{個}}Q_{z}=q_{0}, \dots, q_{i}, \overbrace{q_{i+1}, \dots, q_{i+j}, q_{i+1}, \dots, q_{i+j}}^{\text{$q_{i+1}, \dots, q_{i+j}$ の反復が $m$回}}, q_{i+j+1}, \dots, q_{k}$$ は記号列 $xy^{m}z$ による $\mathautomaton{A}$ の状態遷移である。 $q_{0}=q_{I}$, $q_{k}\in F$ であるから、$xy^{m}z$ は $\mathautomaton{A}$ に受理される。 $\qed$

反復補題の補足

本稿の反復補題の $|xy|\leq n$ という条件を外したものも反復補題と呼ばれる。 反復補題の証明中において、$w$ の部分列を考えたことがそれ以外の条件の証明に対して非本質的であることに注意すると、 $|xy|\leq n$ という条件が余計であると考えられるからであろう。

$\emptyword$ 動作なしの有限オートマトン

この項では $\emptyword$ 動作なしの有限オートマトン(finite automaton without $\emptyword$-transitions) について述べる.

$\emptyword$ 動作なしの有限オートマトンの定義

有限オートマトン $\mathautomaton{A}=(Q, \Sigma, \Delta, q_{I}, F)$ が 次の条件を満たすとき、 $\mathautomaton{A}$ は $\emptyword$ 動作なしの有限オートマトン(finite automaton without $\emptyword$-transitions)である と言う。

  • $(q, a, q')\in \Delta$ に対して $a=\emptyword$ ならば $q=q'$

命題 3

任意の有限オートマトンに対して、 それと等価な$\emptyword$ 動作なしの有限オートマトンが存在する。

命題 3 の証明

Now writing.......

参考文献

  1. 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
  2. 五十嵐喜英他、『数理情報科学シリーズ 24 オートマトンと形式言語の基礎?』、牧野書店、2011
  3. Martin Aigner,Guenter M. Ziegler,Karl H. Hofmann, [["Proofs from THE BOOK"]], Springer, 2004

関連項目

Chomsky 階層

文法のタイプ言語のクラス計算モデル
タイプ0句構造言語Turingマシン?
タイプ1文脈依存言語線形有界オートマトン?
タイプ2文脈自由言語プッシュダウン・オートマトン?
タイプ3正規言語有限オートマトン


*1 Martin Aigner,Guenter M. Ziegler,Karl H. Hofmann, [["Proofs from THE BOOK"]], Springer, 2004 によると、一般に定理が補題と呼ばれる条件は「広範囲の応用例を持つ」「一見して完璧に明らか」「証明も含めて美しい」の三条件を満たすことである。

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-12-21 (月) 01:36:10 (138d)