Download presentation
Presentation is loading. Please wait.
1
形式言語とオートマトン Formal Languages and Automata 第４日目
Tokyo University of Technology School of Computer Science Hiroyuki KAMEDA
2
今日の内容 前回の復習 最簡型DFAの求め方とその練習 正規表現を最簡型オートマトンで表現 など 確認問題：
正規表現を最簡型オートマトンで表現 など 確認問題： 最簡型DFAとは何だったでしょうか？ 正規表現ってどんなものでしたでしょうか？ ©東京工科大学 2014年5月13日 亀田弘之
3
今日の学習目標 ε-NFAが与えられたとき，それと能力的に等価なFAを構築できる。
©東京工科大学 2014年5月13日 亀田弘之
4
これと同等なDFAを求める． 今日の目標 教科書p.59問題2.4より
【ポイント】 「非決定性の有限オートマトン」と 能力的に等価な「決定性の有限オートマトン」を求める。 ©東京工科大学 2014年5月13日 亀田弘之
5
これと同等なmin-FAを求める． 今日の目標 教科書p.59問題2.5より
【ポイント】 能力的に等価な 決定性の有限オートマトンのうち、 状態数が最も少ないものを求める。 ©東京工科大学 2014年5月13日 亀田弘之
6
今日の目標 課題：これ同等なDFAを求めよ． ©東京工科大学 2014年5月13日 亀田弘之
7
DFA Md からmin-DFA Ms を求める
重要 DFA Md からmin-DFA Ms を求める Md の状態を，Fの状態と非Fの状態との２グループに分割する． 各グループの各状態について，入力における遷移先が同じグループに行くものとそうでないものとに分割する． どのグループもこれ以上分割することができなくなるまで２を繰り返す． 最終的に得られる各グループそれぞれを新たな状態とみなすことで得られるDFAがMs . ©東京工科大学 2014年5月13日 亀田弘之
8
DFA Md からmin-DFA Ms を求める
重要 DFA Md からmin-DFA Ms を求める Md の状態を，Fの状態と非Fの状態との２グループに分割する． 各グループの各状態について，入力における遷移先が同じグループに行くものとそうでないものとに分割する． どのグループもこれ以上分割することができなくなるまで２を繰り返す． 最終的に得られる各グループそれぞれを新たな状態とみなすことで得られるDFAがMs . 問 上記の青丸○の付いた用語の意味を 自分の言葉で説明しなさい。 ©東京工科大学 2014年5月13日 亀田弘之
9
例による解説 ©東京工科大学 2014年5月13日 亀田弘之
10
このオートマトン M = <Q, Σ, δ, q0, F> を詳しく分析してみよう！
入力アルファベット Σ 初期状態: 最終状態 F 状態遷移関数δ： ©東京工科大学 2014年5月13日 亀田弘之
11
このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう
状態の集合 Q = { q0, q1, q2, q3, q4, q5 } 入力アルファベット Σ = { 0, 1 } 初期状態: q0 最終状態 F = { q3, q5 } 状態遷移関数δ： 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学 2014年5月13日 亀田弘之
12
状態集合Qを分割してみよう QをFと非Fとに分割： Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } 手順１はこれでおしまい． ©東京工科大学 2014年5月13日 亀田弘之
13
手順2(1) Q11 = { q0, q1, q2, q4 } と Q12= { q3, q5 } をそれぞれ調べる。
©東京工科大学 2014年5月13日 亀田弘之
14
手順2(2) 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3
1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学 2014年5月13日 亀田弘之
15
手順２（３） Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } } ©東京工科大学 2014年5月13日 亀田弘之
16
手順2（４） 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3
1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 ©東京工科大学 2014年5月13日 亀田弘之
17
手順２（３） 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 } } ©東京工科大学 2014年5月13日 亀田弘之
18
手順2（５） 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3
1 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5 これで収束しました！ ©東京工科大学 2014年5月13日 亀田弘之
19
手順２（３） 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つに分けること（分割）ができた！） ©東京工科大学 2014年5月13日 亀田弘之
20
手順３(1) min-DFAの内部状態は4つ． qA { q0, q4 } qB { q1 } qC { q2 } qD { q3, q5 } ©東京工科大学 2014年5月13日 亀田弘之
21
手順３(2) qA qC qB qD 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5
1 内 部 状 態 q0 q4 q1 q2 q3 q5 min-DFAの内部状態は４つ． qA { q0, q4 } qB { q1 } qC { q2 } qD { q3, q5 } qA qB qC 1 qD ©東京工科大学 2014年5月13日 亀田弘之
22
一般のDFAから最簡形DFAを 求める方法わかりましたでしょうか？
この内容は 重要です！ 一般のDFAから最簡形DFAを 求める方法わかりましたでしょうか？ qA qB qC 1 qD ©東京工科大学 2014年5月13日 亀田弘之
23
ここまで、良いでしょうか？ ©東京工科大学 2014年5月13日 亀田弘之
24
練習問題 プリントで配布します。 ©東京工科大学 2014年5月13日 亀田弘之
25
次の話題 次は、NFAと同等なDFAを求める方法に ついて知ろう！
There exists a theory, such that for any NFA we can build a DFA equivalent to it. (任意のNFAに対して、それと等価なDFAが存在する、という定理がある。) ©東京工科大学 2014年5月13日 亀田弘之
26
例えばこれと同等なDFAを求めたい． これはNFAです。 教科書p.59問題2.4より ©東京工科大学 2014年5月13日 亀田弘之
27
例題：まずはこれから！ これもNFAです。 ©東京工科大学 2014年5月13日 亀田弘之
28
アルゴリズム2.1(教科書p.47) （ここだけを読んでも、普通の人ならば俄かにはわかりませんよね。こんな時は落ち着いて、順番にやって行きましょう！） 黒板で説明します。億考えながらメモを取ってください。 ©東京工科大学 2014年5月13日 亀田弘之
29
自習問題１：等価なDFAを求めよ。 ©東京工科大学 2014年5月13日 亀田弘之
30
自習問題２：等価なDFAを求めよ。 ©東京工科大学 2014年5月13日 亀田弘之
31
最後の話題 正規表現を最簡型オートマトンで表現する． 正規表現 α ＝＞ NFA ＝＞ min-DFA 例：α=a(a|b)*bb のNFA，min-DFAを求める． これは総合演習でもあるので、次回話します！ お疲れ様 ©東京工科大学 2014年5月13日 亀田弘之
Similar presentations
