平成20年10月5日（月） 東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "平成20年10月5日（月） 東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 δ ： 状態遷移関数 δ（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

16 δ ： 状態遷移関数 δ（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 内部入力

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

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

19 つまり

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34 練習問題

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

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

37 例

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

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

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

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

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

43 練習問題

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

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

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

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

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

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

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

51 続きは自由課題です。

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

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