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

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

今日のクイズ 次の内、オートマトンではないものはどれか？ 自動販売機 からくり人形 自転車 弓曳童子 （http://digimoba.com/products/yumihiki/yumihiki.html）

第１部

今日は有限オートマトンの話 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 ： 状態の集合( 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×Σ∋( qi , a) → 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と書いたりするようだ。 FAは入力テープとヘッドから構成されている。 入力テープはセルに分かれていて、入力記号が並んでいる。 ヘッドには内部状態があり、状態には、初期状態と最終状態がある。 初期状態は１つだが、最終状態は複数個あってもいいようだ。 そして、．．．

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

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

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

初めに内部状態ありき 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

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

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

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

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

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

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

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

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

練習問題

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

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

練習問題３ 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 }

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

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

第２部

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

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

例（教科書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 }

ε非決定性有限オートマトン 空動作を許容する非決定性有限オートマトン (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 「条件を順次緩めた」 ということは、より多くの文字列を受理できる？ つまり、より大きな言語・より多様な言語を受理することができる？

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

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

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

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

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

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

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

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