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

第1版
形式言語とオートマトン2013
ー第9日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
今日の内容
1. 練習・練習また練習
2. Pumping定理とその応用
3. Myhill-Nerodeの定理
2
第１部練習
3
練習問題
• まず練習問題をやってみよう。
所要時間は１０分。
提出は不要ですが、試験対策になるので、
各自自力で解いてみてください。
4
問題最簡形DFAを求めよ。
5
解法手順
1. 状態遷移表を作ってみる。
2. 到達不能状態を除去する。
3. 状態遷移表を見て、決定性か非決定性かを
確認する。
4. （以下、省略）
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
初期状態 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
上記の表から，決定性有限オートマトンであることがわかる。
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
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 } }
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
収束した。
状態は５つであることが分かった。
0
b
1
f
e
g
a
h
c
c
f
f
g
h
c
g
g
g
e
c
11
第２部理論編
13
ポンピングの補題
• 言語 L は DFA M により受理されるとする。こ
のときある定整数 n が存在して，z∊L， |z| ≧n
なる z は，z=uvw， |uv| ≦n， |v|≧1 のように
分解され，かつ，uviw ∊ L となる。
（この補題は様々な証明等で役立ちます。
大学院へ進みたい人は押さえること！）
14
ポンピングの補題適用例
• 次の言語が正規言語でないことを示せ。
L  {a b | n  1}
n n
15
ポンピングの補題の考察
b
a
f
c
e
16
17
（ポンピングの補題適用例）
問題次の言語が正規言語でないことを示せ。
L  {a b | n  1}
n n
18
証明
言語 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 ×
19
注意事項
• ポンピングの補題は、言語Lが正規言語であ
るための必要条件であり、必要十分条件では
n m m
ない。例えば、言語L’=｛ c a b ｝は、ポンピン
グの補題を満たすが、正規言語ではない。
n i
(c c)c (a b )  L
i
m m
20
MyHill-Nerodeの定理
• 次の３つの命題は同値である。
1. 言語 L  * は正規言語である。
2. L は、指数が有限かつ右不変な * 上の
同値関係 R による同値類の和として表わされる。
3. 任意の z  * に対して、
xz  L  yz  L
のとき x  L y と定義すると、 *上の２項関係
 L は指数が有限な同値関係である。
21
証明のための準備
•
•
•
•
同値関係
*
*
関数  (q, x )   ( (q, x), )
同値類
同値関係の指数
22
関係
• 集合 X と Y の直積 X  Y に対して、
その部分集合 R  X  Y を２項関係、
あるいは、単に関係という。
• ( x, y)  R のとき、x と yは「 R の関係にある」と
いい、 xRy と書く。
• R  X  X のとき、RはX上の関係と呼ぶ。
23
関係の例
• （板書します）
24
同値関係
• Ａ上の関係Rが以下の条件を満たすとき、
関係Rのことを特に同値関係と呼ぶ。
1. xRx for any x∈Ａ.
2. xRy  yRx for any x, y ∈Ａ.
3. xRy かつyRz ⇒ xRz for any x, y, z ∈Ａ.
25
同値関係の例
• X=Z（整数全体の集合）とする。
このとき、x,y∊Zに対して、
x-y が５の倍数  xRy
と書くことにすると、RはZ上の１つの同値関係
である。
• Zは同値関係Rにより、５つの類に分割される。
• 同値関係の指数とは、同値類の個数のことで
ある。従って、今の場合Rの指数は５である。
26
同値関係Rが右不変
• xRyのとき、xzRyzが成り立つこと。
27
例
• xRy  δ*(q0, x) = δ*(q0, y)
のとき、
xRy
⇒ δ*(q0, x) = δ*(q0, y)
⇒ δ*(δ*(q0, x),z) = δ*(δ*(q0, y),z)
⇒ δ*(q0, xz) = δ*(q0, yz)
⇒ xzRyz
for z∊Σ*
関係Rは右不変
28
問題
1.
2.
3.
4.
関係の例を２つ以上挙げよ。
同値関係の例を２つ以上挙げよ。
modulo n の同値類は全部で何個あるか？
内部状態がm個のDFAは、入力文字列を幾
つの同値類に分割するか？
29

Download Report