オートマトンと言語

形式言語とオートマトン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
1
b
b
a
2
f
a
b
b
3
非決定性有限オートマトンの定義
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
f1
f2
NFA M3の状態遷移図
a, b
b
a
i
ε
a
2
f2
ε遷移(非決定性の要因)
1
a, b
b
f1
ここまでは定義の復習
もう少し具体例を
• 教科書の
– 図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
の5つ組として記述しなさい。
練習問題(続き)
•
教科書の
①
②
③
④
⑤
図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.
ファイル名が file で始まるもの
ファイル名に file が含まれているもの
ファイル名が 2 で終わっているもの
ファイル名末尾に3桁の数字が付いているもの
こんなとき、正規表現が活躍する
(自由課題)調べてみよう
• Linuxでの ls コマンド
• Linuxでの grep コマンド or egrep コマンド
などでの正規表現(メタ文字)はどうなっているか?
(注)これらは、本授業で取り扱う正規表現とは少し
異なっています。いわば拡張正規表現となっていま
す。本授業の正規表現が、本来の正規表現です。
参考文献
・詳説 正規表現, Jeffrey E. F. Friedl, O’Reilly Japan(2003).
これからの話の流れ
これからの話の流れ
正規表現 ー> NFA
NFA
ー> DFA
DFA
ー> 状態数最小DFA
(例で詳しく練習しますので、しっかり付いて
来てください。)
それでは正規表現の定義から
• 正規表現は、文字列の集合を表現・記述する。
• 正規表現は言語を記述する。
• 例えば、正規表現 a|b は 文字列 a と b の2
つを意味する。
つまり。正規表現 a|b = { a, b } といった具合。
正規表現の例
• 文字 a だけからなる言語 { a } は正規表現で
a と書く。
• 文字列 abc だけからなる言語 { abc } は正
規表現で abc と書く。
• 言語 { aaa } は正規表現で aaa または a3 と
書く。
• 言語 { a, b } は正規表現で a|b または a+b
と書く。
正規表現の例(2)
• 言語 { a, aa, aaa, aaaa, aaaaa, …. } は
正規表現で a† と書く。(“a ダガー”と読む)
• 空文字列は正規表現の1つで、εと書く。
(“エプシロン”と読む)
• 言語 { ε, b, bb, bbb, bbbb, …} は正規表現
で b* と書く。
(“b アスタリスク”とか“b スター”とか”b星印”
などと読む)
(参考) asterisk , epsilon
正規表現の定義
1. 空文字列記号εは空文字列を意味する正規表現。
2. 文字 x がアルファベット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
f1
2.R=a
a
1
f1
3.R|S
R
f1
1
S
4.RS
1
R
S
f1
5.R*
ε
ε
ε
1
R
ε
f1
練習
• 次の正規表現αをFAで表現しなさい。
α= a(a|b)*bb
教科書pp.143-147 参照のこと。
練習はまた次回の復習でやりましょう
次のそして今日最後の話し
• 状態数が少ないFAの存在とその求め方
M1の状態遷移図
a
i
a
a
1
b
b
a
2
f
a
b
b
3
M1が受理する文字列は?
a
i
a
a
1
b
b
a
2
f
a
b
b
3
M1が受理する文字列は?
• 例えば、
(考えてみてください。)
M1と等価なFAの状態遷移図(No.2)
a
i
a
b
a
1,2
f
a
b
b
3
FA と L(G) との関係
• 正規文法G
• 正規言語L(G)
• 有限オートマトンM
L(G)
M1
M2
M3
• 1つのL(G)に対して、複数のFAがあり得る。
• 能力的に等価なFAがある。
用語定義と問題提起
• 能力的に等価なFA群のうち、状態数が最も
少ないものを、「最少化FA」あるいは「最簡形
FA」と呼ぶことにしよう。
• 「最簡形FA」は、どうやって求めたらいいのだ
ろうか?
一般的な手続きはどうなっているのか?
(注)このようなFAの存在はOKですよね。
Why?(考えてみてください。)
Myhill-Nerodeの定理
• いま、受理・生成能力が同じFAの中で、状態
数が最も少ないFA(最簡型FA)を求めたい。
その理論的根拠を与えてくれるのが標記の
定理である。
理論的にはとても
重要な定理
ちょっとだけ覗いてみよう!
Myhill-Nerode関係
• 定義: 到達不可能
⇔ 初期状態から到達することのできないこと。
そのような状態を到達不可能状態と呼ぶ。
• 定理: 到達不可能状態は、O( |K| |Σ| )で見
出される。
• 定義: FAの2つの状態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を2つに分
割する。 n=0とおく。
2. 任意のnについて、Pnの細分化を行い、そ
の結果を、Pn+1とする。
3. Pn = Pn+1 となりまで手順2を繰り返す。
具体例で練習しましょう
• 図2.18 (p.53)
今日はここまで。お疲れ様。
• URL:
http://kameken.clique.jp/
の右下を見てください。
• 次回は、今回までの復習と第3章です。
余力があったら予習してみてください。