形式言語とオートマトン2016 ー有限オートマトンー 第4日目

Presentation on theme: "形式言語とオートマトン2016 ー有限オートマトンー 第4日目"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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