形式言語とオートマトン2011 ー有限オートマトンー 第３日目 Tokyo University of Technology School of Computer Science 平成23年5月10日

今日のポイント 有限オートマトン（復習・確認） 正規表現 (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? 「入力アルファベット」とは、 テープ上に配列される記号群のこと。 なぜ、「入力記号の集合」と呼ばずに、 「入力アルファベット」と呼ぶのでしょか？ それは、テープ上に並べられた記号列は１つの単語を表しているとみなす立場があり、その際、入力記号は単語を構成する文字そのものである。このような文字の集合を一般にはアルファベット(字母)と呼ぶためである。 なお、本講義では入力記号ひとつひとつが単語を抽象化したものとする立場をとっています。

例：決定性有限オートマトン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

M1の状態遷移図 状態 入力 a 入力 b i 1 ー 2 3 f i １ ２ ｆ ３ a b

問題 DFA　M1 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa

もう一度DFAの定義から勉強しなおしましょう 問題 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 － 非決定性

M2の状態遷移図 i 1 2 a, b ｆ1 ｆ2 b a 状態 入力a 入力b i i, 2 i, 1 1 ー f1 2 f2 －

問題 FDA M2 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa

もう一度NFAの定義から勉強しなおしましょう 問題 FDA M2 により受理される文字列を５つ以上作ってみなさい。 この問題ができなかった人は、 もう一度NFAの定義から勉強しなおしましょう

NFA M3の状態遷移図 a, b b i 2 ｆ2 a a ε ε遷移（非決定性の要因） 1 a, b b ｆ1

問題 FDA M3 により受理される文字列は次のうちのどれか？ aaaaa aabb abbabb bababaa

もう一度ε-NFAの定義から勉強しなおしましょう 問題 FDA　M3 により受理される文字列を５つ以上作ってみなさい。 この問題ができなかった人は、 もう一度ε-NFAの定義から勉強しなおしましょう

ここまでは定義の復習

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

練習問題 次ページのFA（状態遷移図で記述されている）を、文章の形で記述してみてください。 つまり、FAを の５つ組として記述しなさい。 状態の集合 K 入力アルファベット Σ 状態遷移関数 δ：K×Σ　→ K (表形式でもOK) 初期状態 最終状態の集合F の５つ組として記述しなさい。

練習問題（続き） 教科書の それぞれ。 図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 と書く。 文字列 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の要素ならば、x は { x } を意味する正規表現。 RとSが正規表現ならば、正規表現 R | S あるいは R+S は正規表現Rの表す文字列の集合Aと正規表現Sが表す文字列の集合Bとの和集合。 正規表現 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 } { file0, file1, file2, file3, …, filen, … } { ε, ab, aabb, aaabbb, aaaabbbb, … }

正規表現をFAで表現してみよう （注）このようなことができることは、 　　　数学的に証明されています。 　　　任意の正規表現に対して、それが表す 　　　言語Lをちょうど受理するFAが存在する。　 　　　また、この逆も成り立つ。

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の存在とその求め方

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関係 定義：　到達不可能 ⇔ 初期状態から到達することのできないこと。そのような状態を到達不可能状態と呼ぶ。 定理：　到達不可能状態は、O（ |K| |Σ| ）で 見い出される。 定義(Myhill-Nerodeの関係)： FAの２つの状態pとqが等価 ⇔[δ(p, w) ∈F ⇔δ(q,w)∈F for any w∈Σ*]

Myhill-Nerodeの定理 次の3つの命題は等価である。 アルファベットS上の言語Lが DFAで認識される。 言語L に対し、関係RL は有限指標である。 後日説明します。

この定理で得られる同値類に着目する [p]： pと等価な状態からなる集合（同値類） DFAに対する同値類オートマトン： 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章の最簡型DFAを求める練習です。 余力があったら予習してみてください。

クールダウン問題 問題１ FAとは次のどれのことでしょうか？ ① 有限オートマトン ② アイナルアンサー ③ 英国サッカー協会 問題２ FAにはどんな種類があるか？ 問題３ 正規表現とFAとにはどのような 関係が存在しているか？