形式言語とオートマトン2009 ー第7日目ー

第1版
形式言語とオートマトン2016
ー第7日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
今日の内容
1. 練習・練習また練習
2. Pumping定理
– 紹介
– 応用例
– 証明
3. Myhill-Nerodeの定理
H28年度形式言語とオートマトン（東京工科大学）
2
第１部練習（訓練）
H28年度形式言語とオートマトン（東京工科大学）
3
練習問題
• まず練習問題をやってみよう。
• 所要時間は15分。
• 試験対策になるので、各自自力で解いてみて
ください。
• 周りの仲間と相談してもいいです。
– お互い教え合ってください。
– お互い聞き合ってください。
– 他利的に行動してください。
H28年度形式言語とオートマトン（東京工科大学）
4
問題1 最簡形DFAを求めよ。
H28年度形式言語とオートマトン（東京工科大学）
5
解法手順
1. 状態遷移表を作ってみる。
2. 到達不能状態を除去する。
3. 状態遷移表を見て、決定性か非決定性かを
確認する。
4. （以下、省略）
H28年度形式言語とオートマトン（東京工科大学）
6
状態遷移表の作成
a
b
c
d
e
f
g
h
0
b
g
a
c
h
c
g
g
1
f
c
c
g
f
g
e
c
H28年度
形式言語とオートマトン（東京工科大学）
初期状態
a から状態
d には到達不可能
7
新しい状態遷移表
a
b
c
e
f
g
h
0
b
g
a
h
c
g
g
1
f
c
c
f
g
e
c
H28年度形式言語とオートマトン（東京工科大学）
上記の表から，決定性有限オートマトンであることがわかる。
8
状態の分割
1. { a, b, c, e, f, g, h } => { ①{a, b, e, f, g, h}, ②{ c } }
2. a -> (b,f) -> (①，①)
0
1
b -> (g,c) -> (①，②)
a
b
f
c -> (a,c) -> (①，②)
b
g
c
e -> (h,f) -> (①，①)
c
a
c
f -> (c,g) -> (②，①)
e
h
f
g -> (g,e) -> (①，①)
f
c
g
h -> (g,c) -> (①，②)
g
g
e
=> { { a, e, g }, { b, h }, { f }, { c } }
h
g
c
H28年度形式言語とオートマトン（東京工科大学）
9
3. { ①{ a, e, g }, ②{ b, h }, ③{ f }, ④{ c } }
a -> (b,f) -> (②，③)
e -> (h,f) -> (②，③)
g -> (g,e) -> (①，①)
h -> (g,c) -> (①，④)
b -> (g,c) -> (①，④)
=> { { a, e }, { g }, { b, h }, { f }, { c } }
H28年度形式言語とオートマトン（東京工科大学）
a
b
0
b
g
1
f
c
c
e
f
a
h
c
c
f
g
g
h
g
g
e
c
10
4. { ①{ a, e }, ②{ g }, ③{ b, h }, ④{ f }, ⑤{ c } }
a -> (b,f) -> (③，④)
e -> (h,f) -> (③，④)
a
b -> (g,c) -> (②，⑤)
b
h -> (g,c) -> (②，⑤)
c
収束した。
状態は５つであることが分かった。
H28年度形式言語とオートマトン（東京工科大学）
0
b
1
f
e
g
a
h
c
c
f
f
g
h
c
g
g
g
e
c
11
その他の問題は、
授業時に紙で配布します。
Practice makes perfect.
H28年度形式言語とオートマトン（東京工科大学）
13
今日の一言
Mathematics is the gate and key to the
sciences.（中略） Neglect of mathematics
works injury to all knowledge, since he
who is ignorant of it cannot know the other
sciences or the things of this world. And
what is worse, men who are ignorant are
unable to perceive their ignorance and so
do not seek a remedy. ー Roger Bacon
H28年度形式言語とオートマトン（東京工科大学）
14
第２部理論編
H28年度形式言語とオートマトン（東京工科大学）
15
ポンピングの補題
• 言語 L は DFA M により受理されるとする。こ
のときある定整数 n が存在して，z∊L， |z| ≧n
なる z は，z=uvw， |uv| ≦n， |v|≧1 のように
分解され，かつ，uviw ∊ L となる。
（この補題は様々な証明等で役立ちます。
大学院へ進みたい人は押さえること！）
H28年度形式言語とオートマトン（東京工科大学）
16
ポンピングの補題適用例
• 次の言語が正規言語でないことを示せ。
L  {a b | n  1}
n n
H28年度形式言語とオートマトン（東京工科大学）
17
ポンピングの補題の考察
b
a
c
f
H28年度形式言語とオートマトン（東京工科大学）
e
18
ポンピングの補題適用例（再）
問題次の言語が正規言語でないことを示せ。
L  {a b | n  1}
n n
H28年度形式言語とオートマトン（東京工科大学）
19
証明
言語 L = { anbn | n = 1, 2, 3, 4, … } が正規言語で
あると仮定すると，言語Lはポンピングの補題を
満たす。つまり， anbn は，uvw と分解される。
いま， anbn = a a a … a b b b … bより，
1)anbn = a … v a … a b … b ×
2)anbn = a … a … a v b … b ×
3)anbn = a … a … a b … v … b ×
H28年度形式言語とオートマトン（東京工科大学）
20
注意事項
• ポンピングの補題は、言語Lが正規言語であ
るための必要条件であり、必要十分条件では
n m m
ない。例えば、言語L’=｛
c ｝は、ポンピン
a b
グの補題を満たすが、正規言語ではない。
n i
(c c )c ( a b )  L
i
m m
H28年度形式言語とオートマトン（東京工科大学）
21
MyHill-Nerodeの定理
• 次の３つの命題は同値である。
1. 言語 L  * は正規言語である。
2. L は、指数が有限かつ右不変な  * 上の
同値関係 R による同値類の和として表わされる。
3. 任意の z  * に対して、
xz  L  yz  L
のとき x  L y と定義すると、  *上の２項関係
 L は指数が有限な同値関係である。
H28年度形式言語とオートマトン（東京工科大学）
22
定理を理解するための予備知識
•
•
•
•
同値関係
*
*

(
q
,
x

)


( (q, x),  )
関数
同値類
同値関係の指数
H28年度形式言語とオートマトン（東京工科大学）
23
関係
• 集合 X と Y の直積 X  Y に対して、
その部分集合 R  X  Y を２項関係、
あるいは、単に関係という。
• ( x, y )  R のとき、x と yは「 R の関係にある」と
いい、 xRy と書く。
• R  X  X のとき、RはX上の関係と呼ぶ。
H28年度形式言語とオートマトン（東京工科大学）
24
関係の例
• （板書します）
H28年度形式言語とオートマトン（東京工科大学）
25
同値関係
• Ａ上の関係Rが以下の条件を満たすとき、
関係Rのことを特に同値関係と呼ぶ。
1. xRx for any x∈Ａ.
2. xRy  yRx for any x, y ∈Ａ.
3. xRy かつyRz ⇒ xRz for any x, y, z ∈Ａ.
H28年度形式言語とオートマトン（東京工科大学）
26
同値関係の例
• X=Z（整数全体の集合）とする。
このとき、x,y∊Zに対して、
x-y が５の倍数  xRy
と書くことにすると、RはZ上の１つの同値関係
である。
• Zは同値関係Rにより、５つの類に分割される。
• 同値関係の指数とは、同値類の個数のことで
ある。従って、今の場合Rの指数は５である。
H28年度形式言語とオートマトン（東京工科大学）
27
同値関係Rが右不変
• xRyのとき、xzRyzが成り立つこと。
H28年度形式言語とオートマトン（東京工科大学）
28
例
• xRy  δ*(q0, x) = δ*(q0, y)
のとき、
xRy
⇒ δ*(q0, x) = δ*(q0, y)
⇒ δ*(δ*(q0, x),z) = δ*(δ*(q0, y),z)
⇒ δ*(q0, xz) = δ*(q0, yz)
⇒ xzRyz
for z∊Σ*
関係Rは右不変
H28年度形式言語とオートマトン（東京工科大学）
29
挑戦問題
1. 関係の例を２つ以上挙げよ。
2. 同値関係の例を２つ以上挙げよ。
3. modulo n の同値類は全部で何個あるか
(つまり、指数はいくらか)？
4. 内部状態がm個のDFAは、入力文字列を幾
つの同値類に分割するか？
H28年度形式言語とオートマトン（東京工科大学）
30
次回は、いよいよ
チーリングマシンです！
H28年度形式言語とオートマトン（東京工科大学）
31

Download Report