平成20年10月5日（月） 東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2009 -B(後半)- 平成20年10月5日（月） 東京工科大学 コンピュータサイエンス学部 亀田弘之

後半はオートマトンの話 automaton (複数形は,automata) 敢えて訳せば「自動機械」でしたね。 教科書の第４章（字句解析）を理解するのに不可欠ですので、じっくりと学びましょう。 もっと詳しく学びたい人へ [1] 米田（監修）：オートマトン・言語理論の基礎，近代科学社 [2] 言語理論とオートマトン，サイエンス社　など

オートマトンとは オートマトン ＝ 自動機械 (automaton, pl. automata) もっと具体的には… いったいどんなものなのかなぁ

まずは有限オートマトンから Finite Automaton(FA) 何がfinite（有限）か？ もっと詳しく見ていきましょう！ ＝＞　内部状態数が有限 もっと詳しく見ていきましょう！

有限オートマトンのイメージ FAの概観 a1 a2 ai-1 ai an ・・・ ・・・ ・・・ qk

有限オートマトンのイメージ FAの概観 入力記号 セル an ai a1 a2 ai-1 ・・・ 入力テープ qk 内部状態 ヘッド

有限オートマトンのイメージ qk FAの概観 a1 a2 ai-1 ai an セル 入力記号 入力テープ ヘッド 内部状態 ・・・ ・・・

このようなハードウェアをもった自動機械が、入力記号を読みながら内部状態を変化させていく、といったもの。 言葉で表現すると次のようになる。

有限オートマトンの定義 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( qi , a ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K ) なるほどそうですか でも、よくわからないなぁ

それでは、具体例をみてみましょう。

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( qi , a ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { r, s, t } 状態の集合 Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { r, s, t } 状態の集合 Σ ：　{ a, b }入力アルファベット δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { r, s, t } 状態の集合 Σ ：　{ a, b }入力アルファベット δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

δ ： 状態遷移関数 δ（r, a）＝s, δ（r, b）＝r, δ（s, a）＝t, δ（s, b）＝r, δ ：　状態遷移関数 δ（r, a）＝s, δ（r, b）＝r, δ（s, a）＝t, δ（s, b）＝r, δ（t, a）＝t, δ（t, b）＝r 状態 入力 次の状態 r a s b t

δ ： 状態遷移関数 δ（r, a）＝s, δ（r, b）＝r, δ（s, a）＝t, δ（s, b）＝r, δ ：　状態遷移関数 外部入力 δ（r, a）＝s, δ（r, b）＝r, δ（s, a）＝t, δ（s, b）＝r, δ（t, a）＝t, δ（t, b）＝r 状態 入力 次の状態 r a s b t 内部入力

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { r, s, t } 状態の集合 Σ ：　{ a, b }入力アルファベット δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　r 初期状態 F ：　最終状態の集合 ( F ⊆ K )

有限オートマトンの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { r, s, t } 状態の集合 Σ ：　{ a, b }入力アルファベット δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　r 初期状態 F ：　{ t } 最終状態の集合 ( F ⊆ K )

つまり

有限オートマトンの例 K = { r, s, t} , Σ= { a, b }入力アルファベット, q0 = r, F ={ t }, δ ：　 状態 入力 次の状態 r a s b t

このFAを動作させてみましょう 入力文字列 abaa bababa aabbaabb

以上のFAは決定性FAともいう 決定性有限オートマトン （Deterministic FA; DFA） ？？？ 後で、 非決定性オートマトン(Non-deterministic finite automaton; NFA) が出てきます。

FAの視覚的表記法 言葉よりも図の方が分かりやすいこともある。 便利なので覚えましょう。簡単です！ よかったぁ

初めに内部状態ありき s r t

δ：状態遷移関数をみながら… δ（r, a）＝s, δ（r, b）＝r, δ（s, a）＝t, δ（s, b）＝r, δ（t, a）＝t, δ（t, b）＝r 状態 入力 次の状態 r a s b t

遷移の条件と行き先を記入 s a r t

遷移の条件と行き先を記入 s a r t b

遷移の条件と行き先を記入 s a a r t b

遷移の条件と行き先を記入 s a a b r t b

遷移の条件と行き先を記入 s a a b r t a b

遷移の条件と行き先を記入 s a a b r b t a b

初期状態と最終状態を記入 s a a b r b t a b

もう一度動作させてみよう 入力文字列 abaa bababa aabbaabb

練習問題

以上のFAは決定性FAという 決定性有限オートマトン （Deterministic FA; DFA） 次に、非決定性有限オートマトン （Non-deterministic Finite Automaton; NFA）

非決定性有限オートマトンの定義 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 K×Σ∋( a, qi ) → (qk, ql,…,qm)∈ 2K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

例

ε非決定性有限オートマトン 空動作を許容する非決定性有限オートマトン (non-deterministic FA with ε; ε-NFA)

ε非決定性有限オートマトンの定義 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 K×(Σ∪{ε})∋ → 2K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

Ε-NFAの例 FA = ( K, Σ, δ, q0, F ) ただし、 K ： { p, q, r} 状態の集合 Σ ：　{ 0, 1 }入力アルファベット δ ：　状態遷移関数 δ： K×(Σ∪{ε})∋ → 2K q0 ：　p 初期状態 F ：　{ q, r } 最終状態の集合

δ：状態遷移関数 δ(p,ε)＝{ q, r } δ(q,0)＝{ q } δ(r,1)＝{ r },

状態遷移図にすると… (自分で書いてみよう) 検討：このオートマトンはどんな文字列を 受理するのだろうか？

練習問題

注意事項 DFA －＞ NFA －＞ ε-NFA 「条件を順次緩めた」 ということは、より多くの文字列を受理できる？ つまり、より大きな言語・より多様な言語を受理することができる？

いいえ 違います 本当なの？！ あら、残念…

FA, NFA, ε-NFA は同等の能力 （言語の生成・受理の能力として） ε-NFAをFAに、それも状態数が最小のFAに変換する方法について学ぼう！ （教科書のp.61あたりに書いてあります。） 次回は、まず、p.29あたりからはじめます。

次の話題 Backus Naur Form (構文要素の記述) 構文図式(構文の視覚的表示) 文法（構文の形式的記述） 構文木（構文構造の視覚的表示） 正規表現＝FA ε-NFA -> NFA -> FA -> 状態数最少FA FAのプログラムへの変換 LEX（プログラムの自動生成）

付録 オートマトンの動作イメージ 動作の初めの部分のみ 興味のある人は続きを自分で作ってみてください。

有限オートマトンの動作 FAの概観 a1 a2 ai-1 ai an ・・・ ・・・ ・・・ qk

有限オートマトンの動作 FAの概観 a b a a q X q’ r a s b t r s

続きは自由課題です。

ここまでのまとめ 文字列認識装置としてのオートマトンを復讐した。

とうことは、 #include <stdio.h> int main( ) { int x; x = 10; x += 5; printf(“xの値は=%d“, x); } このようなものを認識できるオートマトンが作れるってこと？