vxy

講義URL:
http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html
※ 文字化けしてしまう場合はブラウザのエンコードを変更してみて下さい
形式言語とオートマトン
第12回回答例
山中克久
練習問題
練習問題12-1
言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語で
ないことを証明せよ
練習問題12-1
言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語で
ないことを証明せよ
証明 L={ai bj ck | i ≤ j ≤ k } が文脈自由言語であると仮定
文脈自由言語に対する反復補題（定理4.12）を
w = ambmcm に適用することを考える．
w = ambmcm は，反復補題の条件を満たすように
5つの部分系列 uvxyz にできる
w = a m b m cm =
u
v
x
反復補題の条件
（1）任意の i ≥ 0 に対して，uvixyiz ∊ L，
（2） |vy| ≥ 1
（3） |vxy| ≤ m
y
z
練習問題12-1
言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語で
ないことを証明せよ
証明（続き）
vxy の位置によって場合分け
（まずは，場合分けの仕方を説明）
vxy
vxy
aaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccc
vxy
vxy
- vxy が cm の領域と重ならない場合
- vxy が am の領域と重ならない場合
に分けて考えてみよう
vxy
練習問題12-1
言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語で
ないことを証明せよ
証明（続き）
vxy が cm の領域と重ならない場合
vxy
vxy
aaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccc
vxy
vxy
必ず uv2xy2z ∉ L となる à 矛盾
vxy
v = aa…abb…b または y = aa…abb…b となる場合は，
明らかに uv2xy2z ∉ L になる
そうでない場合は（ex. v = aa…a），uv2xy2z = apbqcm とすると，
p > m または q > m の少なくともどちらか一方が成立
練習問題12-1
言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語で
ないことを証明せよ
証明（続き）
vxy が am の領域と重ならない場合
vxy
vxy
aaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccc
vxy
vxy
vxy
v = aa…abb…b または y = aa…abb…b となる場合は，
明らかに uv2xy2z ∉ L になる
そうでない場合は（ex. v = bb…b），uv0xy0z = ambrcs とすると，
m > r または m > s の少なくともどちらか一方が成立

Download Report