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

形式言語とオートマトン2010
ー第8日目ー
東京工科大学
コンピュータサイエンス学部
亀田弘之
練習問題
• まず練習問題をやってみよう。
10分程度でやってみましょう。
提出は不要ですが、試験対策になるので、
各自自力で解いてみてください。
2
問題 最簡形DFAを求めよ。
3
解法手順
1. 状態遷移表を作ってみる。
2. 到達不能状態を除去する。
3. 状態遷移表を見て、決定性か非決定性かを
確認する。
4. (以下、省略)
4
解答例
5
ここでちょっと一休み?
• 授業評価アンケートを取ります。
6
MyHill-Nerodeの定理
• 次の3つの命題は同値である。
1. 言語 L  * は正規言語である。
2. L は指数が有限かつ右不変な *上の
同値関係 R による同値類の和として表わされる。
3. 任意の z  * に対して、
xz  L  yz  L
のとき x  L y と定義すると、 *上の2項関係
 L は指数が有限な同値関係である。
7
証明のための準備
•
•
•
•
同値関係
*
*
関数  (q, x )   ( (q, x), )
同値類
同値関係の指数
8
関係
• 集合 X と Y の直積 X  Y に対して、
その部分集合 R  X  Y を2項関係、
あるいは、単に関係という。
• ( x, y)  R のとき、x と yは「 R の関係にある」と
いい、 xRy と書く。
• R  X  X のとき、RはX上の関係と呼ぶ。
9
同値関係
• A上の関係Rが以下の条件を満たすとき、関
係Rのことを特に同値関係と呼ぶ。
1. xRx for any x∈A.
2. xRy  yRx for any x, y ∈A.
3. xRy かつyRz ⇒ xRz for any x, y, z ∈A.
10
同値関係の例
• X=Z(整数全体の集合)とする。
このとき、x,y∊Zに対して、
x-y が5の倍数  xRy
と書くことにすると、RはZ上の1つの同値関係
である。
• Zは同値関係Rにより、5つの類に分割される。
• 同値関係の指数とは、同値類の個数のことで
ある。従って、今の場合Rの指数は5である。
11
同値関係Rが右不変
• xRyのとき、xzRyzが成り立つこと。
12
例
• xRy  δ*(q0, x) = δ*(q0, y)
のとき、
xRy
⇒ δ*(q0, x) = δ*(q0, y)
⇒ δ*(δ*(q0, x),z) = δ*(δ*(q0, y),z)
⇒ δ*(q0, xz) = δ*(q0, yz)
⇒ xzRyz
for z∊Σ*
関係Rは右不変
13
問題
1.
2.
3.
4.
関係の例を2つ以上挙げよ。
同値関係の例を2つ以上挙げよ。
modulo n の同値類は全部で何個あるか?
内部状態がm個のDFAは、入力文字列を幾
つの同値類に分割するか?
(この問題の意味は曖昧であることに注意せ
よ)
14
おまけ
• ポンピングの補題
– 言語LはDFA M により受理されるとする。このとき
ある定整数nが存在して、z∊L, |z| ≧n なるzは、
z=uvw, |uv| ≦n, |v|≧1 のように分解され、かつ、
uviw ∊ L となる。
(この補題は、さまざまな定理の証明に役立つ。)
15