形式言語とオートマトン2008 ー有限オートマトンー Tokyo University of Technology School of Computer Science 今日のポイント • • • • 有限オートマトン（復習・確認）正規表現正規表現とオートマトンの関係最簡型オートマトンの作り方（DFA －＞ min-DFA）まずは、復習から言語(文法)とオートマトン ---------------------------------------------------------------言語処理装置 ---------------------------------------------------------------• 句構造言語(PSL) ⇔ Turing 機械 • 文脈依存言語(CSL) ⇔ 線形有界オートマトン • 文脈自由言語(CFL) ⇔ プッシュダウンオートマトン • 正規言語(RL) ⇔ 有限オートマトン ---------------------------------------------------------------まずはここからかじってみようかな計算モデルやプログラミング言語設計に深くかかわっています。さて、… 有限オートマトンとは（復習） • (英) Finite Automaton (FA) finite automata (pl.) いろいろなFA • Finite Automaton – Deterministic Finite Automaton (DFA) or Deterministic Finite State Machine – Nondeterministic Finite Automaton (NFA) or Nondeterministic Finite State Machine – NFA-ε or NFA with ε moves or NFA-lambda 英語も覚えましょう決定性有限オートマトンの定義 DFA M = ( K, Σ, δ, q0, F ) ただし、 K ：状態の集合( Kは有限集合) Σ ：入力アルファベット（Σは有限集合） δ ：状態遷移関数 δ： K×Σ∋(qi , a ) → qj ∈ K q0 ：初期状態 F ：最終状態の集合 ( F ⊆ K ) 例：決定性有限オートマトンM1 DFA M1 = ( K, Σ, δ, q0, F ) ただし、 K ： { i, f, 1, 2, 3} Σ ： { a, b } δ ：状態遷移関数（次の頁参照） q0 ： i F ： {f} 状態遷移関数δ 状態入力 a 入力 b i 1 ー 1 2 3 2 3 f 2 2 2 3 f f M1の状態遷移図 a i a a １ b b a ２ｆ a b b ３非決定性有限オートマトンの定義 NFA M = ( K, Σ, δ, q0, F ) ただし、 K ：状態の集合( Kは有限集合) Σ ：入力アルファベット（Σは有限集合） δ ：状態遷移関数 δ： K×Σ∋(qi, a ) → Q ⊂ K q0 ：初期状態 F ：最終状態の集合 ( F ⊆ K ) 例：非決定性有限オートマトンM2 NFA M2 = ( K, Σ, δ, q0, F ) ただし、 K ： { i, f1, f2, 1, 2 } Σ ： { a, b } δ ：状態遷移関数（次の頁参照） q0 ： i F ： { f1, f2 } 状態遷移関数δ 状態入力a 入力b i i, 2 i, 1 1 ー f1 2 f1 f2 f2 f1 f2 － f1 f2 非決定性 M2の状態遷移図 a, b a, b a i a 2 b 1 a, b b ｆ1 ｆ2 NFA M3の状態遷移図 a, b b a i ε a 2 ｆ2 ε遷移（非決定性の要因） 1 a, b b ｆ1 ここまでは定義の復習もう少し具体例を • 教科書の – 図2.8 (p.37) – 問2.3 (p.39) – 図2.9 (p.41) – 問2.4 (p.43) – 図2.11 (p.45) などを見なれること。図の意味（FAの動作）が分かるようになりましょう。練習問題 • 次ページのFA（状態遷移図で記述されている）を、文章の形で記述してみてください。つまり、FAを – 状態の集合 K – 入力アルファベット Σ – 状態遷移関数 δ：K×Σ → K (表形式でもOK) – 初期状態 – 最終状態の集合F の５つ組として記述しなさい。練習問題（続き） • 教科書の ① ② ③ ④ ⑤ 図2.8 (p.37) 問2.3 (p.39) 図2.9 (p.41) 問2.4 (p.43) 図2.11 (p.45) それぞれ。新しい話に入りましょう！ • 正規表現 (regular expressions) 正規表現は文字列の集合を現すのに便利！ CSにとっては常識です。例えば、… • 設定： – とあるディレクトリに以下のファイルがある file1 file2 file3 outfile1 outfile2 • infile1 infile12 tmpfile102 README123 問題：ファイルを名前で探したい 1. 2. 3. 4. ファイル名がｆile で始まるものファイル名に file が含まれているものファイル名が 2 で終わっているものファイル名末尾に３桁の数字が付いているものこんなとき、正規表現が活躍する（自由課題）調べてみよう • Linuxでの ls コマンド • Linuxでの grep コマンド or egrep コマンドなどでの正規表現（メタ文字）はどうなっているか？（注）これらは、本授業で取り扱う正規表現とは少し異なっています。いわば拡張正規表現となっています。本授業の正規表現が、本来の正規表現です。参考文献・詳説正規表現, Jeffrey E. F. Friedl, O’Reilly Japan(2003). これからの話の流れこれからの話の流れ正規表現ー＞ NFA NFA ー＞ DFA DFA ー＞状態数最小DFA （例で詳しく練習しますので、しっかり付いて来てください。）それでは正規表現の定義から • 正規表現は、文字列の集合を表現・記述する。 • 正規表現は言語を記述する。 • 例えば、正規表現 a|b は文字列 a と b の２つを意味する。つまり。正規表現 a|b = { a, b } といった具合。正規表現の例 • 文字 a だけからなる言語 { a } は正規表現で a と書く。 • 文字列 abc だけからなる言語 { abc } は正規表現で abc と書く。 • 言語 { aaa } は正規表現で aaa または a3 と書く。 • 言語 { a, b } は正規表現で a|b または a+b と書く。正規表現の例（２） • 言語 { a, aa, aaa, aaaa, aaaaa, …. } は正規表現で a† と書く。（“a ダガー”と読む） • 空文字列は正規表現の１つで、εと書く。（“エプシロン”と読む） • 言語 { ε, b, bb, bbb, bbbb, …} は正規表現で b* と書く。（“b アスタリスク”とか“b スター”とか”b星印” などと読む） (参考) asterisk , epsilon 正規表現の定義 1. 空文字列記号εは空文字列を意味する正規表現。 2. 文字ｘがアルファベットAの要素ならば、x は { x } を意味する正規表現。 3. RとSが正規表現ならば、正規表現 R | S あるいは R+S は正規表現Rの表す文字列の集合Aと正規表現Sが表す文字列の集合Bとの和集合。 4. 正規表現 R・S あるいは RS は、Rの表す文字と Sの表す文字とを連結した（その順に並べた）したものすべてからなる集合。 5. Rが正規表現ならば、 R*は、Rの表す文字をゼロ個以上連接した（並べた）ものすべてからなる集合。正規表現の定義（再）アルファベットA上の正規表現とは、以下の規則によって作られるもの（表現）のことである。 1. 空文字列εは正規表現である。 2. Aの要素 x ( x∈A ) は正規表現である。 3. RとSがともに正規表現ならば、 R|S RS R* はいずれも正規表現である。練習：対応する言語は？ • • • • • • abcd a* ab* (ab)* bc(2|4)* a†bcd* 例：A = { a, b, c } 上の正規表現 • • • • • • • ε a c acb ab|b c(cb|a) a(a|b)*cba 練習：正規表現で書いてみよう • { automaton } • { file0, file1, file2, file3, …, filen, … } • { ε, ab, aabb, aaabbb, aaaabbbb, … } 正規表現をFAで表現してみよう • （注）このようなことができることは、証明されています。 1. R=ε ε 1 ｆ1 2.R=a a 1 ｆ1 3.R｜S R ｆ1 1 S 4.RS 1 R S ｆ1 5.R* ε ε ε 1 R ε ｆ1 練習 • 次の正規表現αをFAで表現しなさい。 α＝ a(a|b)*bb 教科書pp.143-147 参照のこと。練習はまた次回の復習でやりましょう次のそして今日最後の話し • 状態数が少ないFAの存在とその求め方 M1の状態遷移図 a i a a １ b b a ２ｆ a b b ３ M1が受理する文字列は？ a i a a １ b b a ２ｆ a b b ３ M1が受理する文字列は？ • 例えば、（考えてみてください。） M1と等価なFAの状態遷移図(No.2) a i a b a 1,2 ｆ a b b 3 FA と L(G) との関係 • 正規文法G • 正規言語L(G) • 有限オートマトンM L(G) M１ M2 M3 • １つのL(G)に対して、複数のFAがあり得る。 • 能力的に等価なFAがある。用語定義と問題提起 • 能力的に等価なFA群のうち、状態数が最も少ないものを、「最少化FA」あるいは「最簡形 FA」と呼ぶことにしよう。 • 「最簡形FA」は、どうやって求めたらいいのだろうか？一般的な手続きはどうなっているのか？（注）このようなFAの存在はOKですよね。 Why?（考えてみてください。） Myhill-Nerodeの定理 • いま、受理・生成能力が同じFAの中で、状態数が最も少ないFA（最簡型FA）を求めたい。その理論的根拠を与えてくれるのが標記の定理である。理論的にはとても重要な定理ちょっとだけ覗いてみよう！ Myhill-Nerode関係 • 定義：到達不可能 ⇔ 初期状態から到達することのできないこと。そのような状態を到達不可能状態と呼ぶ。 • 定理：到達不可能状態は、O（ |K| |Σ| ）で見出される。 • 定義： FAの２つの状態pとqが等価 ⇔[δ(p, w) ∈F ⇔δ(q,w)∈F for any w∈Σ*] Myhill-Nerodeの定理次の3つの命題は等価である。 1. アルファベットS上の言語LがDFAで認識される。 2. 言語L は、ある右不変でかつ有限指標でもある同値関係における同値類の和集合である。 3. 言語L に対し、関係RL は有限指標である。この定理で得られる同値類に着目する • [p]： pと等価な状態からなる集合（同値類） • DFAに対する同値類オートマトン： Q’={[q]| q∈Q} Σ’=Σ q0’=[q0] F’={[q]| q∈F} δ’([q], a) = [δ(q,a)] 得られる知見 • 定理：同値類オートマトンA’はもとのFA A’ と同じ言語を受理する。 • Myhill-Nerodeの定理を証明する際に、この同値類の作り方も得られる。その作り方が、最簡型DFA作成手順そのものとなっている。こんな理屈もあるが、… • 後日詳しくやりましょう。いまは気にしないでおきましょう。最簡化FAの求め方 • いろいろ知られている。 • わかりやすいものは以下のものです。最簡型DFAを求める手順重要 1. P0 = { F, K-F } 状態の集合Kを２つに分割する。 n=0とおく。 2. 任意のnについて、Pnの細分化を行い、その結果を、Pn+1とする。 3. Pn = Pn+1 となりまで手順２を繰り返す。具体例で練習しましょう • 図2.18 (p.53) 今日はここまで。お疲れ様。 • URL: http://kameken.clique.jp/ の右下を見てください。 • 次回は、今回までの復習と第３章です。余力があったら予習してみてください。