形式言語とオートマトン Formal Languages and Automata 第４日目

Presentation on theme: "形式言語とオートマトン Formal Languages and Automata 第４日目"— Presentation transcript:

1 形式言語とオートマトン Formal Languages and Automata 第４日目
Tokyo University of Technology School of Computer Science Hiroyuki KAMEDA

2 今日の内容 前回の復習 最簡型DFAの求め方とその練習 正規表現を最簡型オートマトンで表現　など

3 これと同等なDFAを求める． 教科書p.59問題2.4より

4 これと同等なmin-FAを求める． 教科書p.59問題2.5より

5 課題：これ同等なDFAを求めよ．

6 まずは，復習から （皆さんも一緒にやってみましょう！）

7 DFA Md からmin-DFA Ms を求める
復習 DFA Md からmin-DFA Ms を求める Md の状態を，Fの状態と非Fの状態との２グループに分割する． 各グループの各状態について，入力における遷移先が同じグループに行くものとそうでないものとに分割する． どのグループもこれ以上分割することができなくなるまで２を繰り返す． 最終的に得られる各グループそれぞれを新たな状態とみなすことで得られるDFAがMs .

8 例による解説

9 このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう
入力アルファベット Σ 初期状態: 最終状態 F 状態遷移関数δ：

10 このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう
状態の集合 Q = { q0, q1, q2, q3, q4, q5 } 入力アルファベット Σ = { 0, 1 } 初期状態: q0 最終状態 F = { q3, q5 } 状態遷移関数δ： 入力記号 1 内 部 状 態 q0 q4 q1 q2 q3 q5

11 状態集合Qを分割してみよう QをFと非Fとに分割： Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } 手順１はこれでおしまい．

12 手順2(1) Q11 = { q0, q1, q2, q4 } と　Q12= { q3, q5 } を調べていく．

13 手順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

14 手順２（３） Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } }

15 手順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

16 手順２（３） 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 } }

17 手順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 これで収束したね！

18 手順２（３） 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つに分けることができた！）

19 手順３(1) min-DFAの内部状態は4つ． qA  { q0, q4 } qB  { q1 } qC  { q2 } qD  { q3, q5 }

20 手順３(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

21 一般のDFAから最簡形DFAを 求める方法わかりましたでしょうか？
この内容は試験に 出やすい個所です！ 一般のDFAから最簡形DFAを 求める方法わかりましたでしょうか？ qA qB qC 1 qD

22 次の話題 次は、NFAと同等なDFAを求める方法について知ろう！

23 例えばこれと同等なDFAを求めたい． これはNFAです。 教科書p.59問題2.4より

24 例題：まずはこれから！ これもNFAです。

25 アルゴリズム2.1(教科書p.47) （ここだけを急に読んでもわかりませんよね。順番にやって行きましょう！）
黒板で説明します。メモを取ってください。

26 自習問題１：等価なDFAを求めよ。

27 自習問題２：等価なDFAを求めよ。

28 ここは総合演習でもあるので、次回話しましょう！
最後の話題 正規表現を最簡型オートマトンで表現する． 正規表現　α　＝＞　NFA　＝＞ min-DFA 例：α=a(a|b)*bb のNFA，min-DFAを求める． ここは総合演習でもあるので、次回話しましょう！