配布資料 ppt

Report
形式言語とオートマトン2013
ー有限オートマトンー
第5日目
Tokyo University of Technology
School of Computer Science
© 平成25年5月14日 東京工科大学
今日のポイント
1.
2.
3.
4.
有限オートマトン(復習・確認)
正規表現 (regular expression)
正規表現とオートマトンの関係
最簡型オートマトンの作り方
(DFA -> min-DFA)
超高速オートマトン?
2
形式言語とオートマトン(東京工科大学CS学部)
まずは、復習から
不学
亦而
説時
乎習
之
By Confucius (孔子)
3
形式言語とオートマトン(東京工科大学CS学部)
言語(文法)とオートマトンの関係
---------------------------------------------------------------言語 (languages)
処理装置 (devices)
---------------------------------------------------------------• 句構造言語(PSL)
⇔
Turing 機械
• 文脈依存言語(CSL) ⇔
線形有界オートマトン
• 文脈自由言語(CFL) ⇔
プッシュダウンオートマトン
• 正規言語(RL)
⇔
有限オートマトン
---------------------------------------------------------------まずは一番単純
なここからだ!
計算モデル,プログラミング言語設計,
ゲームプログラミング等にも役立ちます。
4
形式言語とオートマトン(東京工科大学CS学部)
さて、…
5
形式言語とオートマトン(東京工科大学CS学部)
有限オートマトンとは(復習)
• (英) Finite Automaton (FA)
finite automata (pl.)
有限オートマトンとは、
内部状態の個数が有限個で
あるオートマトンのことか…
6
形式言語とオートマトン(東京工科大学CS学部)
有限オートマトンとは(その2)
• 左の画像は,機械式タ
イプライタ。
• 状態を持っている。
• 1つの操作により,状態
が順次変わっていく。
• これがオートマトンのイ
メージ。
7
形式言語とオートマトン(東京工科大学CS学部)
いろいろな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
もう見慣れましたよね!
8
形式言語とオートマトン(東京工科大学CS学部)
決定性有限オートマトンの定義
DFA M = ( K, Σ, δ, q0, F )
ただし、
K : 状態の集合( Kは有限集合)
Σ : 入力アルファベット(Σは有限集合)
δ : 状態遷移関数
δ: K×Σ∋(qi , a ) → qj ∈ K
q0 : 初期状態
F : 最終状態の集合 ( F ⊆ K )
9
形式言語とオートマトン(東京工科大学CS学部)
非決定性有限オートマトンの定義
NFA M = ( K, Σ, δ, q0, F )
ただし、
K : 状態の集合( Kは有限集合)
Σ : 入力アルファベット(Σは有限集合)
δ : 状態遷移関数
δ: K×Σ∋(qi, a ) → Q ⊂ K
q0 : 初期状態
F : 最終状態の集合 ( F ⊆ K )
10
形式言語とオートマトン(東京工科大学CS学部)
例:非決定性有限オートマトンM2
NFA M2 = ( K, Σ, δ, q0, F )
ただし、
K : { i, f1, f2, 1, 2 }
Σ : { a, b }
δ : 状態遷移関数
(次の頁参照)
q0 : i
F : { f1, f2 }
11
形式言語とオートマトン(東京工科大学CS学部)
状態遷移関数δ
状態
入力a
入力b
i
i, 2
i, 1
1
ー
f1
2
f1
f2
f2
f1
f2
-
f1
f2
非決定性
12
形式言語とオートマトン(東京工科大学CS学部)
M2の状態遷移図
a, b
a, b
a
i
a
2
f2
b
1
a, b
b
f1
状態
入力a
入力b
i
i, 2
i, 1
1
ー
f1
2
f1
f2
f2
f1
f2
-
f1
f2
13
形式言語とオートマトン(東京工科大学CS学部)
NFA M3の状態遷移図
a, b
b
a
i
ε
a
2
f2
ε遷移(非決定性の要因)
1
a, b
b
f1
14
形式言語とオートマトン(東京工科大学CS学部)
問題
• FDA M3 により受理される文字列は次のうち
のどれか?
①
②
③
④
aaaaa
aabb
abbabb
bababaa
15
形式言語とオートマトン(東京工科大学CS学部)
問題
• FDA M3 により受理される文字列を5つ以上
作ってみなさい。
この問題ができなかった人は、
もう一度ε-NFAの定義から勉強しなおしましょう
16
形式言語とオートマトン(東京工科大学CS学部)
ここまでは定義の復習
17
形式言語とオートマトン(東京工科大学CS学部)
新しい話に入りましょう!
• 正規表現 (regular expressions)
正規表現は文字列の集合を表すのに便利!
CSにとっては常識です。
18
形式言語とオートマトン(東京工科大学CS学部)
これからの話の流れ
正規表現 ー> NFA
NFA
ー> DFA
DFA
ー> 状態数最小DFA
(例で詳しく練習しますので、
しっかり付いて来てください。)
19
形式言語とオートマトン(東京工科大学CS学部)
それでは正規表現の定義から
20
形式言語とオートマトン(東京工科大学CS学部)
ウォーミングアップ
• 正規表現は、文字列の集合を表現・記述する。
• つまり、正規表現は1つの言語を記述する。
• 例えば、正規表現 a|b は 文字列 a と b の2
つを意味する。
この場合は、正規表現 a|b = { a, b } といった
具合。
21
形式言語とオートマトン(東京工科大学CS学部)
正規表現の例
落ち着いて
読んでください
• 文字 a だけからなる言語 { a } は
正規表現では a と書く。
• 文字列 abc だけからなる言語 { abc } は
正規表現で abc と書く。
• 言語 { aaa } は正規表現で
aaa または a3 と書く。
• 言語 { a, b } は正規表現で
a|b または a+b と書く。
ここまではいいですか?
22
形式言語とオートマトン(東京工科大学CS学部)
正規表現の例(2)
• 言語 { a, aa, aaa, aaaa, aaaaa, …. } は
正規表現で a† と書く。(“a ダガー”と読む)
• 空文字列は正規表現の1つで、εと書く。
(“エプシロン”と読む)
• 言語 { ε, b, bb, bbb, bbbb, …} は正規表現
で b* と書く。
(“b アスタリスク”とか“b スター”とか”b星印”
などと読む)
(参考) dagger, asterisk , epsilon
形式言語とオートマトン(東京工科大学CS学部)
23
チャレンジ問題
それでは、正規表現 a|b* が表しているのはつ
ぎのどれですか?
①
②
③
④
{ a, b }
{ a, aa, aaa, ・・・, b, bb, bbb, ・・・ }
{ ε, a, b, bb, bbb, ・・・ }
{ ε ab, abab, ababab, ・・・ }
24
形式言語とオートマトン(東京工科大学CS学部)
ここからが今日の本題です!
• (試験に必ず出ます。)
25
形式言語とオートマトン(東京工科大学CS学部)
正規表現をFAで表現してみよう
(注)このようなことができることは、
数学的に証明されています。
任意の正規表現に対して、それが表す
言語Lをちょうど受理するFAが存在する。
また、この逆も成り立つ。
26
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応(その1)
1. R=ε
ε
i
f1
27
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応(その2)
2.R=a
i
a
f1
28
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応(その3)
3.R|S
R
f1
i
S
29
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応(その4)
4.RS
i
R
S
f1
30
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応(その5)
5.R*
ε
ε
ε
R
i
f1
ε
31
形式言語とオートマトン(東京工科大学CS学部)
練習
1.
2.
3.
4.
5.
正規表現 a
正規表現 b
正規表現 a|b
正規表現 (a|b)*
正規表現 a(a|b)*bb
32
形式言語とオートマトン(東京工科大学CS学部)
練習
多少の修業が
必要です。
• 次の正規表現αをFAで表現しなさい。
α= a(a|b)*bb
33
形式言語とオートマトン(東京工科大学CS学部)
レポート課題No.1
課題 正規表現 α = 0(0|1)*11 を考える。
1.正規表現αを非決定性有限オートマトンで
書き表せ。
2.上記で得られた非決定性有限オートマトンと
等価な決定性有限オートントンを作れ。
提出方法: A4レポート用紙(表紙を付けること)
提出日:平成25年5月21日(火)この授業時間開始時
なお,レポートは答えのみではなく,説明も十分階加える
こと。図表も積極的に使用すると良いですよ。
形式言語とオートマトン(東京工科大学CS学部)
34
今日はここまで。お疲れ様。
• 次回は今回までの復習で
す。正規表現からNFAを
求め,それをDFAに変換
し,さらにはその簡型DFA
を求めます。余力があっ
たら予習しておいてくださ
い。
35
形式言語とオートマトン(東京工科大学CS学部)
今日のポイント(再掲)
1. 復習
1. 有限オートマトン
2. 正規表現 (regular expression)
2. 正規表現とオートマトンの関係
3. NFAからDFAを作る作り方
(NFA → DFA)
4. レポート課題説明
(締め切りは次週)
オートマトンのイメージ
36
形式言語とオートマトン(東京工科大学CS学部)

similar documents