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

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

1 平成26年4月22日（火） 東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2014 -No.2- 平成26年4月22日（火） 東京工科大学 コンピュータサイエンス学部 亀田弘之

2 今日の学習目標 有限オートマトンFAを知る。 FAのイメージをつかみ、定義と動作を知る。 FAに慣れ親しむ。 FAの動作を理解する。

3 今日のクイズ 次の内、オートマトンではないものはどれか？ 自動販売機 からくり人形 自転車 弓曳童子
（

4 第１部

5 今日は有限オートマトンの話 automaton (複数形は,automata) 敢えて訳せば「自動機械」でしたね。
内容は教科書の第２章です。 「計算の原理」を理解するための基礎ですので、じっくりと学びましょう。 もっと詳しく学びたい人へ [1] 言語理論とオートマトン，ホップクロフト・ウルマン，サイエンス社 [2] 形式言語の理論，西野・石坂，丸善　など

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

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

8 有限オートマトンのイメージ FAの概観 a1 a2 ai-1 ai an ・・・ ・・・ ・・・ qk ハードウェア構成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 つまり

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

25 このFAを動作させてみよう！ 入力文字列 abaa bababa aabbaabb （自分で好きな文字列を入力して見よう）

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

27 分かりましたか？

28 分かりましたか？ 「有限オートマトン」というものがあるらしい。 FAと書いたりするようだ。 FAは入力テープとヘッドから構成されている。
入力テープはセルに分かれていて、入力記号が並んでいる。 ヘッドには内部状態があり、状態には、初期状態と最終状態がある。 初期状態は１つだが、最終状態は複数個あってもいいようだ。 そして、．．．

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

30 有限オートマトンの定義 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合)
Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( qi , a ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K ) 理論的形式的 定義だとこうなる

31 これを視覚的に表記すると…

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

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

34 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a r t

35 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a r t b

36 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a a r t b

37 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a a b r t b

38 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a a b r t a b

39 遷移の条件と行き先を記入 状態 入力 次の状態 r a s b t s a a b r b t a b

40 初期状態と最終状態を記入 状態 入力 次の状態 r a s b t s a a b r b t a b

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

42 練習問題

43 自習問題1 本パワーポイントの２１ページのオートマトンに対して、入力文字列　abbaa を与えた場合の一連の動作を、教科書34ページ下に書いてある記号 |- を用いて記述せよ。

44 確認問題２ M = ( K, Σ, δ, q0, F ) の各記号は何か。 K：＿＿＿＿＿＿＿＿ Σ：＿＿＿＿＿＿＿＿ δ：＿＿＿＿＿＿＿＿

45 練習問題３ M1 = ( K, Σ, δ, q0, F ) を状態遷移図表示せよ。 ただし、 K = { q0, q1, q2, q3 }
Σ = { 0, 1 } δ: δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q0, δ(q2,0)=q0, δ(q2,1)=q3, δ(q3,0)=q1, δ(q3,1)=q2 q0 F = { q0 }

46 発展問題４ 問題３で定義されるオートマトンM１が受理する文字列および受理しない（拒否する）文字列をそれぞれ５つずつ例示しなさい。 （注）受理する：accept 　拒絶する：reject これらは専門用語です。

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

48 第２部

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

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

51 例（教科書p.40 例2.4） M22=< Q, Σ, δ, q0, F> Q = { r, s, t }
Σ = { a, b } δ:Q×Σ　→　２Q δ(r,a) = { r, s }, δ(r, b) = { r }, δ(s, a) = { t }, δ(s, b)=φ, δ(t, a) = φ, δ( t, b) =φ Q0 = r F = { t }

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

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

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

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

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

57 練習問題 (今回はなし。次回授業でやりましょう。)

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

59 No! 本当なの？！ あら、残念…

60 DFA, NFA, ε-NFA は同等の能力 （言語の生成・受理の能力として）
ε-NFAをDFAに、それも状態数が最小のFAに変換する方法について学ぼう！ （教科書のp.51あたりに書いてあります。） 次回は、復習をしながら正規表現との関係を話します。

61 宿題（提出不要） 教科書の例題等を確認しておくこと。 例2.1 問2.1 問2.2 問2.3 例2.4 例2.5 問2.5

62 今日のクイズ 次の内オートマトンではないものはどれか？ 有限オートマトンに関する記述として正しいのはどれか？ 自動販売機機械 からくり人形
自転車 有限オートマトンに関する記述として正しいのはどれか？ 状態が無限個ある。 入力記号が無限個ある。 初期状態がある。

63 宿題 q2 q1 q3 提出日時：平成26年4月29日(火)15:00 ・学籍番号 __________
・氏名 ______________ 課題：図の有限オートマトンについて、問いに答えよ。 初期状態はどれか。 　q q q3 最終状態はどれか。 　q q q3 決定性、非決定性どちらか。 決定性　　　非決定性 次の入力文字列の内、 どれが受理されるか。 01 0100 q1 q2 q3 1 0, 1 図．有限オートマトン

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

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

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