スライド 1

形式言語とオートマトン
Formal Languages and Automata
第５日目
Tokyo University of Technology
School of Computer Science
Hiroyuki KAMEDA
There is no genius
that bests hard work.
今日の内容
• 前回の復習も混ぜながら話をします。
• 最簡型DFAの求め方とその練習
• 正規表現を最簡型オートマトンで表現など
確認問題：
1. 最簡型DFAとは何だったでしょうか？
2. 正規表現ってどんなものでしたでしょうか？
2
©東京工科大学 2015年5月19日亀田弘之
今日の修得内容目標
1. ε-NFAが与えられたとき，それと能力的に
等価なFAを構築できる。
2. 任意のFAが与えられたとき，それと能力的
に等価でかつ状態数が最小のFAを構築で
きる。
今日でこれらを身に付けてしまいましょう！
3
©東京工科大学 2015年5月19日亀田弘之
今日の目標
これと同等なDFAを求める．
教科書p.59問題2.4より
【ポイント】「非決定性の有限オートマトン」と
能力的に等価な「決定性の有限オートマトン」を求める。
4
©東京工科大学 2015年5月19日亀田弘之
今日の目標
これと同等なmin-FAを求める．
教科書p.59問題2.5より
【ポイント】能力的に等価な決定性の有限オートマトンのうち、
状態数が最も少ないものを求める。
5
©東京工科大学 2015年5月19日亀田弘之
今日の目標
課題：これと同等なDFAを求めよ．
6
©東京工科大学 2015年5月19日亀田弘之
重要
DFA Md からmin-DFA Ms を求める
1. Md の状態を，F状態と非F状態の
２グループに分割する．
2. 各グループの各状態について，入力におけ
る遷移先が同じグループに行くものとそうで
ないものとに分割する．
3. どのグループもこれ以上分割することがで
きなくなるまで２を繰り返す．
4. 最終的に得られる各グループそれぞれを新
たな状態とみなすことで得られるDFAがMs .
7
©東京工科大学 2015年5月19日亀田弘之
重要
DFA Md からmin-DFA Ms を求める
1. Md の状態を，F状態と非F状態の
２グループに分割する．
2. 各グループの各状態について，入力におけ
る遷移先が同じグループに行くものとそうで
ないものとに分割する．
3. どのグループもこれ以上分割することがで
きなくなるまで２を繰り返す．
4. 最終的に得られる各グループそれぞれを新
たな状態とみなすことで得られるDFAがMs .
問上記の青丸○の付いた用語の意味を
自分の言葉で説明しなさい。
©東京工科大学 2015年5月19日亀田弘之
8
例による解説
9
©東京工科大学 2015年5月19日亀田弘之
このオートマトン M = <Q, Σ, δ, q0, F>
を詳しく分析してみよう！
• 状態の集合
Q
• 入力アルファベット
Σ
• 初期状態:
• 最終状態 F
• 状態遷移関数δ：
10
©東京工科大学 2015年5月19日亀田弘之
このオートマトンM=<Q,Σ,δ,q0, F>
を詳しく分析してみよう
• 状態の集合
Q = { q0, q1, q2, q3, q4, q5 }
• 入力アルファベット
Σ = { 0, 1 }
• 初期状態: q0
• 最終状態 F = { q3, q5 }
• 状態遷移関数δ：
入力記号
0
1
q0
q4
q1
内 q1
部 q
2
状 q
3
態
q4
q2
q4
q1
q3
q5
q2
q0
q1
q5
q3
q2
©東京工科大学 2015年5月19日亀田弘之
11
状態集合Qを分割してみよう
1. QをFと非Fとに分割：
Q = { q0, q1, q2, q3, q4, q5 }
=> Q1 = { { q0, q1, q2, q4 }, { q3, q5 } }
手順１はこれでおしまい．
12
©東京工科大学 2015年5月19日亀田弘之
手順2(1)
• Q11 = { q0, q1, q2, q4 } と Q12= { q3, q5 } をそれ
ぞれ調べる。
©東京工科大学 2015年5月19日亀田弘之
13
手順2(2)
内
部
状
態
q0
q1
q2
q3
q4
q5
入力記号
0
1
q4
q1
q2
q4
q1
q3
q5
q2
q0
q1
q3
q2
内
部
状
態
q0
q1
q2
q4
q3
q5
©東京工科大学 2015年5月19日亀田弘之
入力記号
0
1
q4
q1
q2
q4
q1
q3
q0
q1
q5
q2
q3
q2
14
手順２（３）
2.
Q = { q0, q1, q2, q3, q4, q5 }
=> Q1 = { { q0, q1, q2, q4 }, { q3, q5 } }
=> Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } }
15
©東京工科大学 2015年5月19日亀田弘之
手順2（４）
内
部
状
態
q0
q1
q2
q3
q4
q5
入力記号
0
1
q4
q1
q2
q4
q1
q3
q5
q2
q0
q1
q3
q2
内
部
状
態
q0
q1
q4
q2
q3
q5
©東京工科大学 2015年5月19日亀田弘之
入力記号
0
1
q4
q1
q2
q4
q0
q1
q1
q3
q5
q2
q3
q2
16
手順２（３）
2.
Q = { q0, q1, q2, q3, q4, q5 }
=> Q1 = { { q0, q1, q2, q4 }, { q3, q5 } }
=> Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } }
=> Q3 = { { q0, q4 }, { q1 }, { q2 }, { q3, q5 } }
17
©東京工科大学 2015年5月19日亀田弘之
手順2（５）
内
部
状
態
q0
q1
q2
q3
q4
q5
入力記号
0
1
q4
q1
q2
q4
q1
q3
q5
q2
q0
q1
q3
q2
内
部
状
態
q0
q4
q1
q2
q3
q5
入力記号
0
1
q4
q1
q0
q1
q2
q4
q1
q3
q5
q2
q3
q2
これで収束しました！
18
©東京工科大学 2015年5月19日亀田弘之
手順２（３）
2.
Q = { q0, q1, q2, q3, q4, q5 }
=> Q1 = { { q0, q1, q2, q4 }, { q3, q5 } }
=> Q2 = { { q0, q1, q4 }, { q2 }, { q3, q5 } }
=> Q3 = { { q0, q4 }, { q1 }, { q2 }, { q3, q5 } }
（4つに分けること（分割）ができた！）
19
©東京工科大学 2015年5月19日亀田弘之
手順３(1)
• min-DFAの内部状態は4つ．
qA  { q0, q4 }
qB  { q1 }
qC  { q2 }
qD  { q3, q5 }
20
©東京工科大学 2015年5月19日亀田弘之
手順３(2)
• min-DFAの内部状態は４つ．
qA  { q0, q4 }
内
qB  { q1 }
部
qC  { q2 }
qD  { q3, q5 }
状
態
0
1
qA
1
q0
q4
q1
q2
q3
q5
入力記号
0
1
q4
q1
q0
q1
q2
q4
q1
q3
q5
q2
q3
q2
0
0
qC
qB
0
1
1
qD
21
©東京工科大学 2015年5月19日亀田弘之
この内容は
重要です！
一般のDFAから最簡形DFAを
求める方法わかりましたか？
0
1
qA
1
0
0
qC
qB
0
©東京工科大学 2015年5月19日亀田弘之
1
1
qD
22
ここまで、良いでしょうか？
23
©東京工科大学 2015年5月19日亀田弘之
練習問題
プリントで配布します。
（来週答え合わせをします。自力
で挑戦しておくこと。）
24
©東京工科大学 2015年5月19日亀田弘之
次の話題（復習）
• 次は、NFAと同等なDFAを求める方法に
ついて再確認しよう！
There exists a theory, such that for any NFA we can build
a DFA equivalent to it. (任意のNFAに対して、それと等価な
DFAが存在する、という定理がある。)
25
©東京工科大学 2015年5月19日亀田弘之
例えばこれと同等なDFAを求めたい．
これはNFAです。
教科書p.59問題2.4より
26
©東京工科大学 2015年5月19日亀田弘之
例題：まずはこれから！
これもNFAです。
27
©東京工科大学 2015年5月19日亀田弘之
アルゴリズム2.1(教科書p.47)
• （ここだけを読んでも、普通の人ならば俄かに
はわかりませんよね。こんな時は落ち着いて、
順番にやって行きましょう！）
• 黒板で説明します。よく考えながらメモを取っ
てください。
• そして、何度も練習しましょう。
28
©東京工科大学 2015年5月19日亀田弘之
自習問題１：等価なDFAを求めよ。
29
©東京工科大学 2015年5月19日亀田弘之
自習問題２：等価なDFAを求めよ。
30
©東京工科大学 2015年5月19日亀田弘之
ＦＡに関する最後の話題
• 正規表現を最簡型オートマトンで表現する．
正規表現 α ＝＞ NFA ＝＞ min-DFA
例：α=a(a|b)*bb と等価なmin-DFAを求める．
これは総合演習でもあるので、
次回やりましょう！
31
©東京工科大学 2015年5月19日亀田弘之
お知らせ
本講義は、前期末に定期試験を行います。
32
©東京工科大学 2015年5月19日亀田弘之
補足（練習問題）
• オートマトンに関する練習問題を添えておき
ます。
33
© 東京工科大学亀田弘之
問題
図の有限オートマトンについて、問1-4に答えよ。
1. 初期状態はどれか。
q1
q2
q3
1
2. 最終状態はどれか。
q1
q2
q3
3. 決定性、非決定性のどちらか。
決定性
非決定性
4. 次の入力文字列の内、
受理されるのはどれか。
 0010100
 0101011
 01
 0
 1111111111
 0100
 011010100
 01110111
1
0
q2
q1
0
q3
図．有限オートマトン
0, 1
問題
A群の正規表現が表す文字列の集合は、
それぞれＢ群のどれか？
Ａ群
① あ
② あいう
③ あ+
④ あ*
⑤ あ|い|う
⑥ い|あ
⑦ （あ|い）*
Ｂ群
a.
b.
c.
d.
e.
f.
g.
h.
i.
｛ε｝
｛あ, い｝
｛ ε, あ, ああ, あああ, ・・・｝
｛あ, ああ, あああ, ・・・｝
｛あ, あい, あう, ああい, ああう｝
｛い, いい, いいい, ・・・｝
｛あ｝
｛あ, い, う｝
｛ε, あ, い, ああ, あい, いあ, いい, ・・・｝
© 東京工科大学亀田弘之
35
問題
次の正規表現について、ε-NFA、DFAをそれぞれ求めよ。
1. abb*a
2. (a|b)*a(a|b)
3. (ab|c)*c(bc|a)*
4. (a|b|ε)(ab|b)*bc

Download Report