形式言語とオートマトン

講義URL:
http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html
※ 文字化けしてしまう場合はブラウザのエンコードを変更してみて下さい
形式言語とオートマトン
第6回（練習問題回答例）
山中克久
練習問題
練習問題6-1
以下の言語が正規言語でないことを，（例えば，
教科書の例3.23 のように）きちんと示せ
L = { ww | w ∊ {0,1}* }
※ L中の任意の系列では，同じ系列が2回出現する
練習問題6-1
以下の言語が正規言語でないことを，（例えば，
教科書の例3.23 のように）きちんと示せ
L = { ww | w ∊ {0,1}* }
※ L中の任意の系列では，同じ系列が2回出現する
証明
背理法による．L は正規言語であると仮定する．
L の任意の系列 w について，定理3.22（反復補題）
の条件を満たす m が存在する
w = 0m10m1 とし， w について見ていく
練習問題6-1
以下の言語が正規言語でないことを，（例えば，
教科書の例3.23 のように）きちんと示せ
L = { ww | w ∊ {0,1}* }
証明
w = 0m10m1 ∊ L とし， w について詳しく見ていく
（1）任意の i ≧ 0 に対して xyiz ∊ L，（2） |y| ≧ 1，（3） |xy| ≦ m
w = 0000000000000100000000000001
x
y≠ε
z
≦m
ここで，xy0z = xz は，前半の0の個数と後半の0の
個数が異なるので xz ∉ L である．これは反復補題
に矛盾する

Download Report