形式言語とオートマトン Formal Languages and Automata 第５日目 Tokyo University of Technology School of Computer Science Hiroyuki KAMEDA There is no genius that bests hard work.

©東京工科大学 コンピュータサイエンス学部 亀田弘之 今日の内容 前回の復習も混ぜながら話をします。 最簡型DFAの求め方とその練習 正規表現を最簡型オートマトンで表現　など 確認問題： 最簡型DFAとは何だったでしょうか？ 正規表現ってどんなものでしたでしょうか？ ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学コンピュータサイエンス学部 亀田弘之 今日の修得内容目標 ε-NFAが与えられたとき，それと能力的に等価なFAを構築できる。 任意のFAが与えられたとき，それと能力的に等価でかつ状態数が最小のFAを構築できる。 今日でこれらを身に付けてしまいましょう！ ©東京工科大学コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 今日の目標 これと同等なDFAを求める． 教科書p.59問題2.4より 【ポイント】 「非決定性の有限オートマトン」と 能力的に等価な「決定性の有限オートマトン」を求める。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学コンピュータサイエンス学部 亀田弘之 今日の目標 これと同等なmin-FAを求める． 教科書p.59問題2.5より 【ポイント】 能力的に等価な 決定性の有限オートマトンのうち、 　　　　　　　状態数が最も少ないものを求める。 ©東京工科大学コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 今日の目標 課題：これと同等なDFAを求めよ． ©東京工科大学　コンピュータサイエンス学部　亀田弘之

DFA Md からmin-DFA Ms を求める 重要 DFA Md からmin-DFA Ms を求める Md の状態を，F状態と非F状態の ２グループに分割する． 各グループの各状態について，入力における遷移先が同じグループに行くものとそうでないものとに分割する． どのグループもこれ以上分割することができなくなるまで２を繰り返す． 最終的に得られる各グループそれぞれを新たな状態とみなすことで得られるDFAがMs . ©東京工科大学　コンピュータサイエンス学部　亀田弘之

DFA Md からmin-DFA Ms を求める 重要 DFA Md からmin-DFA Ms を求める Md の状態を，F状態と非F状態の ２グループに分割する． 各グループの各状態について，入力における遷移先が同じグループに行くものとそうでないものとに分割する． どのグループもこれ以上分割することができなくなるまで２を繰り返す． 最終的に得られる各グループそれぞれを新たな状態とみなすことで得られるDFAがMs . 問　上記の青丸○の付いた用語の意味を 　　 自分の言葉で説明しなさい。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 例による解説 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

このオートマトン M = <Q, Σ, δ, q0, F> を詳しく分析してみよう！ 入力アルファベットΣ 初期状態: 最終状態 F 状態遷移関数δ： ©東京工科大学　コンピュータサイエンス学部　亀田弘之

このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう 状態の集合 Q = { q0, q1, q2, q3, q4, q5 } 入力アルファベット Σ = { 0, 1 } 初期状態: q0 最終状態 F = { q3, q5 } 状態遷移関数δ： 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学　コンピュータサイエンス学部

©東京工科大学 コンピュータサイエンス学部 亀田弘之 状態集合Qを分割してみよう QをFと非Fとに分割： Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } 手順１はこれでおしまい． ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 手順2(1) Q11 = { q0, q1, q2, q4 } と　Q12= { q3, q5 } をそれぞれ調べる。 ©東京工科大学　コンピュータサイエンス学部

©東京工科大学 コンピュータサイエンス学部 手順2(2) 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学　コンピュータサイエンス学部

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順２（３） Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } } ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 手順2（４） 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学　コンピュータサイエンス学部

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順２（３） Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } } => Q3 = { { q0, q4 }, { q1 }, { q2 }, { q3, q5 } } ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順2（５） 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 これで収束しました！ ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順２（３） Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } } => Q3 = { { q0, q4 }, { q1 }, { q2 }, { q3, q5 } } （4つに分けること（分割）ができた！） ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順３(1) min-DFAの内部状態は4つ． qA  { q0, q4 } qB  { q1 } qC  { q2 } qD  { q3, q5 } ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 手順３(2) 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 min-DFAの内部状態は４つ． qA  { q0, q4 } qB  { q1 } qC  { q2 } qD  { q3, q5 } qA qB qC 1 qD ©東京工科大学　コンピュータサイエンス学部　亀田弘之

一般のDFAから最簡形DFAを 求める方法わかりましたか？ この内容は重要です！ 一般のDFAから最簡形DFAを 求める方法わかりましたか？ qA qB qC 1 qD ©東京工科大学コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 ここまで、良いでしょうか？ ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 自習：これと同等なDFAを求めよ． プリントで配布します。 （来週答え合わせをします。自力で挑戦しておくこと。） 次回、答え合わせをしましょう。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 次の話題（復習） 次は、NFAと同等なDFAを求める方法に ついて再確認しよう！ There exists a theory, such that for any NFA we can build a DFA equivalent to it. (任意のNFAに対して、それと等価なDFAが存在する、という定理がある。) ©東京工科大学　コンピュータサイエンス学部　亀田弘之

例えばこれと同等なDFAを求めたい． これはNFAです。 教科書p.59問題2.4より ©東京工科大学　2016年5月17日　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 例題：まずはこれから！ これもNFAです。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 アルゴリズム2.1(教科書p.47) （ここだけを読んでも、普通の人ならば俄かにはわかりませんよね。こんな時は落ち着いて、順番にやって行きましょう！） 黒板で説明します。よく考えながらメモを取ってください。 そして、何度も練習しましょう。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 自習問題１：等価なDFAを求めよ。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 自習問題２：等価なDFAを求めよ。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 ＦＡに関する最後の話題 正規表現を最簡型オートマトンで表現する． 正規表現　α　＝＞　NFA　＝＞ min-DFA 例：α=a(a|b)*bb と等価なmin-DFAを求める． これは総合演習でもあるので、次回やりましょう！（事前に挑戦しておいてください） ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 お知らせ 本講義は、前期末に定期試験を行いません。 最終レポート課題にて、成績評価します。 最終レポート課題は、 後日配布します。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 補足（練習問題） オートマトンに関する練習問題（含む、過去問）を添えておきます。 ©東京工科大学　コンピュータサイエンス学部　亀田弘之

©東京工科大学 コンピュータサイエンス学部 亀田弘之 問題 図の有限オートマトンについて、問1-4に答えよ。 初期状態はどれか。 　q1 q2 q3 最終状態はどれか。 　q1 q2 q3 決定性、非決定性のどちらか。 決定性　　　非決定性 次の入力文字列の内、 受理されるのはどれか。 0010100 0101011 01 1111111111 0100 011010100 01110111 q1 q2 q3 1 0, 1 図．有限オートマトン ©東京工科大学　コンピュータサイエンス学部　亀田弘之

A群の正規表現が表す文字列の集合は、 それぞれＢ群のどれか？ 問題 A群の正規表現が表す文字列の集合は、 それぞれＢ群のどれか？ Ａ群 Ｂ群 あ あいう あ+ あ* あ|い|う い|あ （あ|い）* ｛ ε ｝ ｛ あ, い ｝ ｛ ε, あ, ああ, あああ, ・・・｝ ｛ あ, ああ, あああ, ・・・｝ ｛ あ, あい, あう, ああい, ああう ｝ ｛ い, いい, いいい, ・・・｝ ｛あ｝ ｛あ, い, う ｝ ｛ε, あ, い, ああ, あい, いあ, いい, ・・・｝ ©東京工科大学　コンピュータサイエンス学部

©東京工科大学 コンピュータサイエンス学部 亀田弘之 問題 次の正規表現について、ε-NFA、DFAをそれぞれ求めよ。 abb*a (a|b)*a(a|b) (ab|c)*c(bc|a)* (a|b|ε)(ab|b)*bc ©東京工科大学　コンピュータサイエンス学部　亀田弘之