形式言語とオートマトン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学部)
有限オートマトンとは（その２）
• 左の画像は，機械式タ
イプライタ。
• 状態を持っている。
• １つの操作により，状態
が順次変わっていく。
• これがオートマトンのイ
メージ。
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
ｆ2
b
1
a, b
b
ｆ1
状態
入力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
ｆ2
ε遷移（非決定性の要因）
1
a, b
b
ｆ1
14
形式言語とオートマトン(東京工科大学CS学部)
問題
• FDA M3 により受理される文字列は次のうち
のどれか？
①
②
③
④
aaaaa
aabb
abbabb
bababaa
15
形式言語とオートマトン(東京工科大学CS学部)
問題
• FDA M3 により受理される文字列を５つ以上
作ってみなさい。
この問題ができなかった人は、
もう一度ε-NFAの定義から勉強しなおしましょう
16
形式言語とオートマトン(東京工科大学CS学部)
ここまでは定義の復習
17
形式言語とオートマトン(東京工科大学CS学部)
新しい話に入りましょう！
• 正規表現 (regular expressions)
正規表現は文字列の集合を表すのに便利！
CSにとっては常識です。
18
形式言語とオートマトン(東京工科大学CS学部)
これからの話の流れ
正規表現 ー＞ NFA
NFA
ー＞ DFA
DFA
ー＞ 状態数最小DFA
（例で詳しく練習しますので、
しっかり付いて来てください。）
19
形式言語とオートマトン(東京工科大学CS学部)
それでは正規表現の定義から
20
形式言語とオートマトン(東京工科大学CS学部)
ウォーミングアップ
• 正規表現は、文字列の集合を表現・記述する。
• つまり、正規表現は１つの言語を記述する。
• 例えば、正規表現 a|b は 文字列 a と b の２
つを意味する。
この場合は、正規表現 a|b = { a, b } といった
具合。
21
形式言語とオートマトン(東京工科大学CS学部)
正規表現の例
落ち着いて
読んでください
• 文字 a だけからなる言語 { a } は
正規表現では a と書く。
• 文字列 abc だけからなる言語 { abc } は
正規表現で abc と書く。
• 言語 { aaa } は正規表現で
aaa または a3 と書く。
• 言語 { a, b } は正規表現で
a|b または a+b と書く。
ここまではいいですか？
22
形式言語とオートマトン(東京工科大学CS学部)
正規表現の例（２）
• 言語 { a, aa, aaa, aaaa, aaaaa, …. } は
正規表現で a† と書く。（“a ダガー”と読む）
• 空文字列は正規表現の１つで、εと書く。
（“エプシロン”と読む）
• 言語 { ε, 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. R=ε
ε
i
ｆ1
27
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応（その２）
2.R=a
i
a
ｆ1
28
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応（その３）
3.R｜S
R
ｆ1
i
S
29
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応（その４）
4.RS
i
R
S
ｆ1
30
形式言語とオートマトン(東京工科大学CS学部)
正規表現とFAとの対応（その５）
5.R*
ε
ε
ε
R
i
ｆ1
ε
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.１
課題 正規表現 α = 0(0|1)*11 を考える。
1.正規表現αを非決定性有限オートマトンで
書き表せ。
2.上記で得られた非決定性有限オートマトンと
等価な決定性有限オートントンを作れ。
提出方法： A4レポート用紙（表紙を付けること）
提出日：平成２５年５月２１日（火）この授業時間開始時
なお，レポートは答えのみではなく，説明も十分階加える
こと。図表も積極的に使用すると良いですよ。
形式言語とオートマトン(東京工科大学CS学部)
34
今日はここまで。お疲れ様。
• 次回は今回までの復習で
す。正規表現からNFAを
求め，それをDFAに変換
し，さらにはその簡型DFA
を求めます。余力があっ
たら予習しておいてくださ
い。
35
形式言語とオートマトン(東京工科大学CS学部)
今日のポイント(再掲)
1. 復習
1. 有限オートマトン
2. 正規表現 (regular expression)
2. 正規表現とオートマトンの関係
3. NFAからDFAを作る作り方
（NFA → DFA）
4. レポート課題説明
（締め切りは次週）
オートマトンのイメージ
36
形式言語とオートマトン(東京工科大学CS学部)
© Copyright 2024 ExpyDoc
