形式言語とオートマトン2016 ー有限オートマトンー 第4日目 Tokyo University of Technology School of Computer Science © 平成28年4月26日 東京工科大学

今日の話題 有限オートマトン（復習・確認・演習） 正規表現 (regular expression) 正規表現とオートマトンの関係 最簡型オートマトンの作り方 （DFA　－＞　min-DFA） 時間があれば。 場合にによっては次回。 超高速オートマトン! © 東京工科大学 亀田弘之

まずは、復習から 学而時習之 不亦説乎 By Confucius (孔子) © 東京工科大学 亀田弘之

A群の正規表現が表す文字列の集合は、 それぞれＢ群のどれか？ 線で結びなさい。 提出日時：平成27年5月10日(火)10:30 問題 A群の正規表現が表す文字列の集合は、 それぞれＢ群のどれか？ 線で結びなさい。 ・学籍番号 __________ ・氏名 ______________ Ａ群 Ｂ群 あ あいう あ+ あ* あ|い|う い|あ （あ|い）* ｛ あ, い ｝ ｛ あいう ｝ ｛ ε, あ, ああ, あああ, ・・・｝ ｛ あ, ああ, あああ, ・・・｝ ｛ あ, あい, あう, ああい, ああう ｝ ｛ い, いい, いいい, ・・・｝ ｛ あ｝ ｛ あ, い, う ｝ ｛ε, あ, い, ああ, あい, いあ, いい, ・・・｝ © 東京工科大学 亀田弘之

言語(文法)とオートマトンの関係 ---------------------------------------------------------------- 言語 (languages)　　 処理装置 (devices) 句構造言語(PSL) ⇔ Turing 機械 文脈依存言語(CSL) ⇔ 線形有界オートマトン 文脈自由言語(CFL) ⇔ プッシュダウンオートマトン 正規言語(RL) ⇔ 有限オートマトン まずはここからかじってみようかな 計算モデルやプログラミング言語設計に 深くかかわっている話題です。 © 東京工科大学 亀田弘之

さて、… © 東京工科大学 亀田弘之

本講義での当面の話の流れ 正規表現 ー＞ NFA NFA ー＞ DFA DFA ー＞ 最簡型DFA 　（例で詳しく練習しますので、 しっかり付いて来てください。） © 東京工科大学 亀田弘之

正規表現 を FA で表現してみよう （注） このようなことができることは、数学的に証明されています。また，任意の正規表現に対して、それが表す言語Lをちょうど受理するFAが存在します。また、この逆も成り立ちます。 留意点： 「正規表現をFAで表現する」、「FAを正規表現で表現する」とは、どういうことを意味しているのか？ 「正規表現 α と FA M とが等価である」とは、正規表現αが表す文字列全体の集合（言語）と、Mで受理する文字列全体の集合（言語）とが一致することを意味する。 © 東京工科大学 亀田弘之

対応規則(1) R=ε ε i ｆ1 © 東京工科大学 亀田弘之

対応規則(2) 2.R=a a i ｆ1 © 東京工科大学 亀田弘之

対応規則(3) 3.R｜S R i ｆ1 S © 東京工科大学 亀田弘之

対応規則(4) 4.RS i ｆ1 R S © 東京工科大学 亀田弘之

対応規則(5) 5.R* ε ε ｆ1 i ε R ε © 東京工科大学 亀田弘之

練習 次の正規表現αをFAで表現しなさい。 α＝ a(a|b)*bb 多少の修業・訓練が必要です。 教科書pp.143-151 参照のこと。 © 東京工科大学 亀田弘之

この練習（鍛えられます）を今からやります。どうすればできそうか、一緒に考えていきましょう！ © 東京工科大学 亀田弘之

今日最初の話題 状態数が最も少ないFA（状態数最少のFA）の存在とその求め方 © 東京工科大学 亀田弘之

M1の状態遷移図 i １ ２ ｆ ３ a b © 東京工科大学 亀田弘之

M1が受理する文字列は？ i １ ２ ｆ ３ a b © 東京工科大学 亀田弘之

M1が受理する文字列は？ 例えば、 （すでにやりましたが、再度考えてみて 　ください。） © 東京工科大学 亀田弘之

M1と等価なFAの状態遷移図(No.2) i 1,2 3 ｆ a b © 東京工科大学 亀田弘之

定　義 FA同士が等価とはどういう意味？ ２つのFA M1 と M2 とがあり、これらが等価であるとは、 M1 が受理する文字列はM2も受理するとともに、 この逆にM2 が受理する文字列はM1 も受理するということ。 © 東京工科大学 亀田弘之

FA と L(G) との関係 正規文法G 正規言語L(G) 有限オートマトンM １つのL(G)に対して、複数のFAがあり得る。

用語定義と問題提起 能力的に等価なFA群のうち、状態数が最も少ないものを、「最少化FA」あるいは「最簡型FA」と呼ぶことにしよう。 　　（注）このようなFAの存在はOKですよね。 　　　　Why?（考えてみてください。）

ここからはちょっと脇道へ © 東京工科大学 亀田弘之

Myhill-Nerodeの定理 いま、受理・生成能力が同じFAの中で、状態数が最も少ないFA（最簡型FA）を求めたい。その理論的根拠を与えてくれるのが標記のMyhill-Nerodeの定理である。 理論的にはとてもとても重要な定理 © 東京工科大学 亀田弘之

Myhill-Nerode関係 定義： 到達不可能 ⇔ 初期状態から到達することのできないこと。 そのような“状態”を到達不可能状態と呼ぶ。 ちょっとだけ覗いてみよう！ Myhill-Nerode関係 定義：　到達不可能 ⇔ 初期状態から到達することのできないこと。　 　そのような“状態”を到達不可能状態と呼ぶ。 定理：　到達不可能状態は、O（ |K| |Σ| ）の 　　　　　計算量で見い出される。 定義(Myhill-Nerodeの関係)： FAの２つの状態pとqが等価 ⇔[δ(p, w) ∈F ⇔ δ(q,w)∈F for any w∈Σ*] © 東京工科大学 亀田弘之

Myhill-Nerodeの定理 次の3つの命題は等価である。 アルファベットS上の言語Lが DFA M で認識される。 言語L に対し、関係RL は有限指標である。 フーッ，こりゃ大変そうだ… 後日説明します。 © 東京工科大学 亀田弘之

この定理で得られる同値類に着目する [p]： pと等価な状態からなる集合（同値類） DFA M に対する同値類オートマトン： Q’={[q]| q∈Q} Σ’=Σ q0’=[q0] F’={[q]| q∈F} δ’([q], a) = [δ(q,a)] © 東京工科大学 亀田弘之

得られる知見 定理： 同値類オートマトンはもとのFAと同じ言語を受理する。 Myhill-Nerodeの定理を証明する際に、この同値類の作り方もいっしょに得られる。その作り方が、最簡型DFA作成手順そのものとなっている。 © 東京工科大学 亀田弘之

こんな理屈もありますが、… いまは気にしないでおきましょう。 そんなことも学ぶんだぁ。へぇ～. © 東京工科大学 亀田弘之

また、本論へ戻りましょう！ © 東京工科大学 亀田弘之

最簡型FAの求め方 いろいろ知られています。 わかりやすいものは以下のものです。 © 東京工科大学 亀田弘之

最簡DFAを求める手順 重要 P0 = { F, K-F } 状態の集合Kを２つに 分割する。 また、n=0とおく。 任意のnについて、Pnの細分化（分割）を 行い、その結果を、Pn+1とする。 Pn = Pn+1 となるまで手順２を繰り返す。 © 東京工科大学 亀田弘之

具体例で説明しましょう 図2.18 (p.53) これと能力的には等価だが、状態数がより少ないものはあるのか？ あるならばどうやって見つけるのか？ 図2.18 (p.53) © 東京工科大学 亀田弘之

練習問題：次のオートマトンと等価でかつ 最簡型なオートマトンを求めよ。 練習問題：次のオートマトンと等価でかつ　　 　　　　　　　最簡型なオートマトンを求めよ。 i １ ２ ｆ ３ a b © 東京工科大学 亀田弘之

予習問題： 次の正規表現を過不足なく 受理するNFAをそれぞれ示せ。 abba aa(c|d)a aa(c|d)*a ab(a|b)*bb a*cb* © 東京工科大学 亀田弘之

今日の話題(再掲) 復習・確認 Myhill-Nerodeの定理 最簡型オートマトンの作り方 （DFA －＞ min-DFA） 超高速オートマトン？ © 東京工科大学 亀田弘之

クールダウン問題 問題：　「FAにはどんな種類があるのですか？」 　　　 　　　　と聞かれたら、あなたはどう答えますか？ © 東京工科大学 亀田弘之

今日はここまで。お疲れ様。 学而時習之 不亦説乎 次回は、今回までの復習と第2章の最簡型DFAを求める練習です。 常に、復習・練習することを忘れずに！　学んで時にこれを習う、またよろこばしからずや。 By Confucius (孔子) カラーン♪ © 東京工科大学 亀田弘之