形式言語とオートマトン Formal Languages and Automata 第4日目 Tokyo University of Technology School of Computer Science Hiroyuki KAMEDA 今日の内容 • 前回の復習 • 最簡型DFAの求め方とその練習 • 正規表現を最簡型オートマトンで表現 など これと同等なDFAを求める. 教科書p.59問題2.4より これと同等なmin-FAを求める. 教科書p.59問題2.5より 課題:これ同等なDFAを求めよ. まずは,復習から • (皆さんも一緒にやってみましょう!) 復習 DFA Md からmin-DFA Ms を求める 1. Md の状態を,Fの状態と非Fの状態との2 グループに分割する. 2. 各グループの各状態について,入力におけ る遷移先が同じグループに行くものとそうで ないものとに分割する. 3. どのグループもこれ以上分割することがで きなくなるまで2を繰り返す. 4. 最終的に得られる各グループそれぞれを新 たな状態とみなすことで得られるDFAがMs . 例による解説 このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう • 状態の集合 Q • 入力アルファベット Σ • 初期状態: • 最終状態 F • 状態遷移関数δ: このオートマトンM=<Q,Σ,δ,q0, F> を詳しく分析してみよう • 状態の集合 Q = { q0, q1, q2, q3, q4, q5 } • 入力アルファベット Σ = { 0, 1 } • 初期状態: q0 • 最終状態 F = { q3, q5 } • 状態遷移関数δ: 入力記号 0 1 q0 q4 q1 内 q1 部 q 2 状 q 3 態 q4 q2 q4 q1 q3 q5 q2 q0 q1 q5 q3 q2 状態集合Qを分割してみよう 1. QをFと非Fとに分割: Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } 手順1はこれでおしまい. 手順2(1) • Q11 = { q0, q1, q2, q4 } と Q12= { q3, q5 } を調べ ていく. 手順2(2) 内 部 状 態 q0 q1 q2 q3 q4 q5 入力記号 0 1 q4 q1 q2 q4 q1 q3 q5 q2 q0 q1 q3 q2 内 部 状 態 q0 q1 q2 q4 q3 q5 入力記号 0 1 q4 q1 q2 q4 q1 q3 q0 q1 q5 q2 q3 q2 手順2(3) 2. Q = { q0, q1, q2, q3, q4, q5 } => Q1 = { { q0, q1, q2, q4 }, { q3, q5 } } => Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } } 手順2(4) 内 部 状 態 q0 q1 q2 q3 q4 q5 入力記号 0 1 q4 q1 q2 q4 q1 q3 q5 q2 q0 q1 q3 q2 内 部 状 態 q0 q1 q4 q2 q3 q5 入力記号 0 1 q4 q1 q2 q4 q0 q1 q1 q3 q5 q2 q3 q2 手順2(3) 2. 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(5) 内 部 状 態 q0 q1 q2 q3 q4 q5 入力記号 0 1 q4 q1 q2 q4 q1 q3 q5 q2 q0 q1 q3 q2 内 部 状 態 q0 q4 q1 q2 q3 q5 入力記号 0 1 q4 q1 q0 q1 q2 q4 q1 q3 q5 q2 q3 q2 これで収束したね! 手順2(3) 2. 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つに分けることができた!) 手順3(1) • min-DFAの内部状態は4つ. qA { q0, q4 } qB { q1 } qC { q2 } qD { q3, q5 } 手順3(2) • min-DFAの内部状態は4つ. qA { q0, q4 } 内 qB { q1 } 部 qC { q2 } qD { q3, q5 } 状 態 0 1 qA 1 q0 q4 q1 q2 q3 q5 入力記号 0 1 q4 q1 q0 q1 q2 q4 q1 q3 q5 q2 q3 q2 0 0 qC qB 0 1 1 qD この内容は試験に 出やすい個所です! 一般のDFAから最簡形DFAを 求める方法わかりましたでしょうか? 0 1 qA 1 0 0 qC qB 0 1 1 qD 次の話題 • 次は、NFAと同等なDFAを求める方法につい て知ろう! 例えばこれと同等なDFAを求めたい. これはNFAです。 教科書p.59問題2.4より 例題:まずはこれから! これもNFAです。 アルゴリズム2.1(教科書p.47) • (ここだけを急に読んでもわかりませんよね。 順番にやって行きましょう!) • 黒板で説明します。メモを取ってください。 自習問題1:等価なDFAを求めよ。 自習問題2:等価なDFAを求めよ。 最後の話題 • 正規表現を最簡型オートマトンで表現する. 正規表現 α => NFA => min-DFA 例:α=a(a|b)*bb のNFA,min-DFAを求める. ここは総合演習でもあるので、 次回話しましょう!
© Copyright 2024 ExpyDoc