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

今日の話題 有限オートマトン（復習・確認） 正規表現 (regular expression) 正規表現とオートマトンの関係 最簡型オートマトンの作り方 （DFA　－＞　min-DFA） 超高速オートマトン! © 東京工科大学 亀田弘之

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

言語(文法)とオートマトンの関係 ---------------------------------------------------------------- 言語 (languages)　　 処理装置 (devices) 句構造言語(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 ) © 東京工科大学 亀田弘之

ちょっと一言 「入力アルファベット」とは、 テープ上に配列される記号群のこと。 Did you know it? 「入力アルファベット」とは、 テープ上に配列される記号群のこと。 なぜ、「入力記号の集合」と呼ばずに、 「入力アルファベット」と呼ぶのでしょか？ それは、テープ上に並べられた記号列は１つの単語を表しているとみなす立場があり、その際、個々の入力記号は単語を構成する文字そのものである。そしてそのような文字の集合を一般にはアルファベット(字母)と呼ぶためである。 なお、本講義では入力記号ひとつひとつが単語を抽象化したものとする立場をとっています。 © 東京工科大学 亀田弘之

（続き） 英 語 ギ リ シ ア 語 単語 = { ant, book, cool, dog, eleven, …, zebra} 英 語 ギ　リ　シ　ア　語 単語 = { ant, book, cool, dog, eleven, …, zebra} 字母 = { a, b, c, …, z } 単語 = { αγάπη, βέβαια, γλώσσα, ..., ωραίος } 字母 = { α, β, γ, δ, ... , ω } 日 本 語 単語 = { あさ, いぬ, うみ, … , アーカイブ, インク, … , 愛情, 憩い, 歌声, … , 湾岸 } 字母 = { あ, い, う, … , ア,イ, ウ, … , 亜, …, 熙} （注）論理学，数学の立場での定義。 　　　言語学では他の定義を採用することもある。 © 東京工科大学 亀田弘之 閑話休題

例：決定性有限オートマトンM1 DFA M1 = ( K, Σ, δ, q0, F ) ただし、 K ： { i, f, 1, 2, 3} Σ ：　{ a, b } δ ：　状態遷移関数 （次の頁参照） q0 ：　i F ：　{ f } © 東京工科大学 亀田弘之

状態遷移関数δ 状態 入力 a 入力 b i 1 ー 2 3 f © 東京工科大学 亀田弘之

問題1 状態遷移図を示せ。 DFA M1 = ( K, Σ, δ, q0, F ) ただし、 K ： { i, f, 1, 2, 3} 問題1　状態遷移図を示せ。 DFA M1 = ( K, Σ, δ, q0, F ) ただし、 K ：　{ i, f, 1, 2, 3} Σ ：　{ a, b } δ ：　状態遷移関数 q0 ：　i F ：　{ f } 状態 入力 a 入力 b i 1 ー 2 3 f © 東京工科大学 亀田弘之

M1の状態遷移図 状態 入力 a 入力 b i 1 ー 2 3 f i １ ２ ｆ ３ a b © 東京工科大学 亀田弘之

問題2 DFA M1 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa aaaabb © 東京工科大学 亀田弘之

もう一度DFAの定義から勉強しなおしましょう 問題3 DFA　M1 により受理される文字列を５つ以上作りなさい。 この問題ができなかった人は、 もう一度DFAの定義から勉強しなおしましょう © 東京工科大学 亀田弘之

学力定着確認問題 DFA M1 により受理される文字列について以下の問①と②に答えよ。 文字列長が最も短いものを すべて列挙しなさい。 文字列長が４以下のものを すべて列挙しなさい。 学而時習之 不亦説乎 © 東京工科大学 亀田弘之

非決定性有限オートマトンの定義 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 f2 － 非決定性 © 東京工科大学 亀田弘之

問題4 状態遷移図を示せ。 NFA M2 = ( K, Σ, δ, q0, F ) ただし、 K ： { i, f1, f2, 1, 2 } 問題4　状態遷移図を示せ。 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 f2 － © 東京工科大学 亀田弘之

M2の状態遷移図 i 1 2 a, b ｆ1 ｆ2 b a 状態 入力a 入力b i i, 2 i, 1 1 ー f1 2 f2 － © 東京工科大学 亀田弘之

問題5 FDA M2 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa © 東京工科大学 亀田弘之

もう一度NFAの定義から勉強しなおしましょう 問題5 FDA M2 により受理される文字列を５つ以上作りなさい。 この問題ができなかった人は、 もう一度NFAの定義から勉強しなおしましょう © 東京工科大学 亀田弘之

次は，ε-NFA の話し © 東京工科大学 亀田弘之

ε-NFA M3 （状態遷移図表示） i 2 ｆ2 ε遷移（非決定性の要因） 1 ｆ1 a, b b a a ε a, b b © 東京工科大学 亀田弘之

問題６ ε-NFA M3 について以下の問に答えよ。 初期状態はどれか？ 最終状態はどれとどれか？ これは決定性有限オートマトンか？ 文字列 ba を受理するか？ © 東京工科大学 亀田弘之

問題7 ε-NFA M3 により受理される文字列は 次のうちのどれか？ aaaaa aabb abbabb bababaa © 東京工科大学 亀田弘之

もう一度ε-NFAの定義から勉強しなおしましょう 問題7 ε-NFA M3により受理される文字列を５つ以上作りなさい。 この問題ができなかった人は、 もう一度ε-NFAの定義から勉強しなおしましょう © 東京工科大学 亀田弘之

ここまでは定義の復習 © 東京工科大学 亀田弘之

もう少し具体例を 教科書の などを見なれること。図の意味（FAの動作）が 分かるようになりましょう。 図2.8 (p.37) © 東京工科大学 亀田弘之

例えば、図2.8 © 東京工科大学 亀田弘之

確認問題 次ページの状態遷移図で記述されているFA M4を、文章の形で記述してみてください。 つまり、FAを の５つ組として記述しなさい。 状態の集合 K 入力アルファベット Σ 状態遷移関数 δ：K×Σ　→ K (表形式でもOK) 初期状態 最終状態の集合F の５つ組として記述しなさい。 © 東京工科大学 亀田弘之

有限オートマトン　M4 © 東京工科大学 亀田弘之

練習問題（続き） 教科書の それぞれ。 図2.8 (p.37) 問2.3 (p.39) 図2.9 (p.41) 問2.4 (p.43) 　それぞれ。 © 東京工科大学 亀田弘之

新しい話に入りましょう！ 正規表現 (regular expressions) 正規表現は文字列の集合を表すのに便利！ CSにとっては常識です。 © 東京工科大学 亀田弘之

例えば、… 設定： 問題：ファイルを名前で探したい とあるディレクトリに以下のファイルがある ファイル名が ｆile で始まるもの file1 file2 file3 infile1 infile12 outfile1 outfile2 tmpfile102 README123 問題：ファイルを名前で探したい ファイル名が ｆile で始まるもの ファイル名に file が含まれているもの ファイル名が 2 で終わっているもの ファイル名末尾に３桁の数字が付いているもの こんなとき、正規表現が活躍する

（自由課題）調べてみよう Linuxでの ls コマンド Linuxでの grep コマンド または 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 と書く。 落ち着いて 読んでください 正規表現の例 文字 a だけからなる言語 { a } は 正規表現では a と書く。 文字列 abc だけからなる言語 { abc } は 正規表現で abc と書く。 言語 { aaa } は正規表現で aaa または a3 と書く。 言語 { a, b } は正規表現で a|b または a+b と書く。 ここまではいいですか？ © 東京工科大学 亀田弘之

(参考) dagger, asterisk , epsilon 正規表現の例（２） 言語 { a, aa, aaa, aaaa, aaaaa, …. } は 正規表現で a† と書く。（“a ダガー”と読む） 空文字列は正規表現の１つで、εと書く。 （“エプシロン”と読む） 言語 { ε, b, bb, bbb, bbbb, …} は正規表現で b* と書く。 （“b アスタリスク”とか“b スター”とか”b星印”などと読む） (参考) dagger, asterisk , epsilon © 東京工科大学 亀田弘之

ちょっと一言 現代ギリシア文字(24文字)の本当の読み方 Α α アルファ Ι ι イョタ Ρ ρ ロ Β β ヴィタ Κ κ カパ Α α アルファ Ι ι イョタ Ρ ρ ロ Β β ヴィタ Κ κ カパ Σ σ ς シグマ Γ γ ガンマ Λ λ ラムザ Τ τ タフ Δ δ ゼルタ Μ μ ミ Υ υ イプシロン Ε ε エプシロン Ν ν ニ Φ φ フィ Ζ ζ ズィタ Ξ ξ クシ Χ χ ヒ Η η イタ Ο ο オミクロン Ψ ψ プシ Θ θ シタ Π π ピ Ω ω オメガ 留学生の諸君へ：　日本ではギリシャ文字の読み方が人によりバラバラです。 　　　　　　　　　　　　 通常はギリシャ文字を英語読みしたものを採用しています。

チャレンジ問題 それでは、正規表現 a|b* が表しているのは次の①～④のどれですか？ { a, b } { a, aa, aaa, ・・・, b, bb, bbb, ・・・ } { ε, a, b, bb, bbb, ・・・ } { ε ab, abab, ababab, ・・・ } © 東京工科大学 亀田弘之

正規表現の定義 空文字列記号εは空文字列を意味する正規表現。 文字 X がアルファベットAの要素ならば、X は { X } を意味する正規表現。 RとSが正規表現ならば、正規表現 R | S あるいは R+S は正規表現Rの表す文字列の集合Aと正規表現Sが表す文字列の集合Bとの和集合(R∪S)。 正規表現 R・S あるいは RS は、Rの表す文字列とSの表す文字列とをこの順を保って連結した（その順に並べ繋ぎ合せた）文字列すべてからなる集合。 Rが正規表現ならば、 R*は、Rの表す文字列をゼロ個以上連接した（並べた）ものすべてからなる集合。 このような定義文は、正確に述べようとすればするほどますます一般には分かりにくいものになります。すぐに理解できないのは普通です。安心してください。とはいえ、今頑張って（落ち着いて）理解しましょう。

正規表現の定義（再） アルファベットA上の正規表現とは、以下の規則によって作られるもの（表現）のことである。 空文字列εは正規表現である。 Aの要素 x ( x∈A ) は正規表現である。 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 } 練習　正規表現で書いてみよう { automaton } { file0, file1, file2, file3, …, filen, … } { ε, ab, aabb, aaabbb, aaaabbbb, … } 注意！　難問が含まれています。 © 東京工科大学 亀田弘之

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

R=ε ε i ｆ1 © 東京工科大学 亀田弘之

2.R=a a i ｆ1 © 東京工科大学 亀田弘之

3.R｜S R i ｆ1 S © 東京工科大学 亀田弘之

4.RS i ｆ1 R S © 東京工科大学 亀田弘之

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) © 東京工科大学 亀田弘之

今日の話題(再掲) 有限オートマトン（復習・確認） 正規表現 (regular expression) 正規表現とオートマトンの関係 最簡型オートマトンの作り方 （DFA　－＞　min-DFA） 超高速オートマトン？ © 東京工科大学 亀田弘之

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

今日はここまで。お疲れ様。 次回は、今回までの復習と第2章の最簡型DFAを求める練習です。 連休中は大いに遊ぶとともに、復習することを忘れずに！ カラーン♪ © 東京工科大学 亀田弘之