講義URL: http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html ※ 文字化けしてしまう場合はブラウザのエンコードを変更してみて下さい形式言語とオートマトン第13回山中克久目次復習:文脈自由言語の反復補題 l  練習問題回答例 l  プッシュダウンオートマトン l  文脈自由文法の限界正規表現がそうだったように，文脈自由文法で表現できる言語（文脈自由言語）とそうでない言語がある{ an bn cn | n >=0 } 与えられた言語が，正規言語でないことを示すために反復補題を用いた文脈自由言語に関しても，同様に，（文脈自由言語の）反復補題を用いて，与えられた言語が文脈自由言語でないことを示す { an bn | n >=0 } チューリング機械で受理される言語のクラス文脈自由言語のクラス正規言語のクラス反復補題の概要導出木において，同じ変数（下図での変数A）が少なくとも2回出現することに注目変数Aが出現してからもう一度出現するまでの導出を繰り返すことができる S S uとvを反復させる A A A A A u v x y z u v v y x y z （再掲）例4.3: 正しい括弧の系列文脈自由文法 G = （{S}, {（,）}, {S à （S） | SS | ε}, S）は，正しい括弧の系列を生成する（正しい括弧の系列: 開括弧と閉括弧の対応が取れる系列） S S （ S （（ S S ） S ）） S （） ε ε （（（））（））の導出木 S à （S） à （SS） à （（S）S） à （（（S））S） à （（（））S） à （（（））（S）） à （（（））（））定理4.12（文脈自由言語の反復補題）定理4.12 文脈自由言語 L に対して次の条件を満たす正整数 m が存在する．すなわち，L に属する長さが m 以上の任意の系列 w は，適当な u,v,x,y,z ∊ Σ* が存在して，w=uvxyz と表されて，次の3つの条件が満たされる．ここで，|w| は系列 w の長さを表す（1）任意の i ≥ 0 に対して，uvixyiz ∊ L，（2） |vy| ≥ 1 w= u v x y （3） |vxy| ≤ m ※証明は省略 z ∊L 反復補題を例（{0n1n | n≥0}）で確認言語 { 0n1n | n≥0 } は文脈自由言語なので，反復補題が成立するはず m=2 として考える w = 01 として，反復補題が成立するか考える u=ε, v=0, x=ε, y=1, z=ε とすると，3つの条件を満たす（1） uvixyiz ∊ { 0n1n | n≥0 } （2） |vy| ≥ 1 （3） |vxy| ≤ m 定理4.12 文脈自由言語 L に対して次の条件を満たす正整数 m が存在する．すなわち，L に属する長さが m 以上の任意の系列 w は，適当な u,v,x,y,z ∊ Σ* が存在して，w=uvxyz と表されて，次の3つの条件が満たされる．ここで，|w| は系列 w の長さを表す（1）任意の i ≥ 0 に対して，uvixyiz ∊ L，（2） |vy| ≥ 1 （3） |vxy| ≤ m 例4.13 言語 L = {an bn cn | n ≥ 0 } が文脈自由言語でないことを反復補題を用いて示せ証明背理法による反復補題より，3つの条件を満たすな正整数 m が存在して，m 以上の長さをもつ L中の系列 an bn cn に対して，次の2つが成立しなければならない（1） an bn cn が uvxyz と表される（2） uv2xy2z が L に属するこの（1）と（2）が同時に成立することはないことが示されれば，背理法により言語 L は文脈自由文法でないことが導かれる例4.13 言語 L = {an bn cn | n ≥ 0 } が文脈自由言語でないことを反復補題を用いて示せ証明（続き） |vy| ≥ 1 より，v と y の少なくとも一方は空系列でない à 一般性を失うことなく v が空系列ではないと仮定するこのとき v は高々1種類の記号を含むもしそうでないとすると， anbncn は記号の変わる箇所が2箇所だが， uv2xy2z は記号の変わる箇所が4箇所になり矛盾 uv2xy2z = aa … a aa … a bb … b aa … a bb … b bb…b cc … c v v 例4.13 言語 L = {an bn cn | n ≥ 0 } が文脈自由言語でないことを反復補題を用いて示せ証明（さらに続き）（再掲） v は高々1種類の記号を含む v は，an または bn，cn のいずれかに真に含まれる à y についても同様のことが言える uvxyz = aaaaaaaaabbbbbbbbbbcccccccccc v y したがって，uv2xy2z は L に含まれない練習問題練習問題12-1 言語 {ai bj ck | i ≤ j ≤ k } が文脈自由言語でないことを証明せよ有限オートマトンを違った視点で解釈入力テープ 1 0 1 0 1 0 1 0 1 0 1 0 入力ヘッド 0 1 0 1 1 1文字目読み込む 0 1 1 0 1 2文字目読み込む 3文字目読み込む 0 1 0 1 0 1 1 0 1 4文字目読み込む 0 1 1 0 1 1 1 制御部 1 0 1 0 0 終了 0 1 有限オートマトンとプッシュダウンオートマトン入力テープ上の系列を読み取る機械のバリエーション à プッシュダウンオートマトン入力テープ入力テープ入力ヘッド制御部有限オートマトンをテープ読み取り機械として解釈した図入力ヘッドトップスタックヘッド制御部スタックプッシュダウンオートマトンプッシュダウンオートマトンの動きテープヘッドの記号aと，スタックヘッドの記号b，現在の状態q から，次の状態 q’ と，スタックへ書込む系列 u が決まる v a w v w u 状態 q’ z テープの a を読み，スタックの u を読み，状態 q’ になって，スタックのトップの系列 b を u に上書き（q’,u） ∊ δ（q,a,b） b z a v a w 状態 q u 状態 q’ z テープのε を読み，（何も読み込まず），スタックの u を読み，状態 q’ になって，スタックのトップの系列 b を u に上書き（q’,u） ∊ δ（q,ε,b） PDA プッシュダウンオートマトン（PushDown Automaton, PDA）とは6項組 M = （Q, Σ, Γ, δ, q0, F）である．ここで， P（A）は, 集合A （1） Qは状態の有限集合のべき集合（2）Σは入力アルファベット（3）Γはスタックアルファベット（4）δ: Q × Σε × Γε à P（Q × Γ*）は状態遷移関数（5）q0 ∊ Q は開始状態（6）F ∊ Q は受理状態の集合 ※ Σε = Σ∪{ε}, Γε = Γ∪{ε} ※ P（Q×Γ*）は, {（q1,u1）, … , （qm,um）} と書いてもよいただし，q1,…,qm ∊ Q，u1,…,um ∊ Γ* （非決定的な遷移関数になっていることに注意）再掲: プッシュダウンオートマトンの動きテープヘッドの記号aと，スタックヘッドの記号b，現在の状態q から，次の状態 q’ と，スタックへ書込む系列 u が決まる v a w v a w u 状態 q’ q a,b à u q’ z （q’,u） ∊ δ（q,a,b） b z v 状態 q a w u 状態 q’ q ε,b à u z （q’,u） ∊ δ（q,ε,b） q’ 例5.2: { 0n1n | n≥0 } のPDA start q1 ε,ε à $ q2 0,ε à 0 1,0 à ε q4 ε,$ à ε q3 1,0 à ε 気持ち 0を読み込む à スタックに0を貯める 1を読み込む à スタック中の0を1つ消す PDA を M = （Q, Σ, Γ, δ, q0, F）とする系列wの受理スタックが空からスタート Q = {q1,q2,q3,q4}, Σ = {0,1}, Γ = {0, $}, w を読み込む δ（q1,ε,ε） = {（q2,$）} δ（q2,0,ε） = {（q2,0）}, δ（q2,1,0） = {（q3,ε）} スタックが空でかつ受理 δ（q3,1,0） = {（q3,ε）}, δ（q3,ε,$） = {（q4,ε）} 状態で終わるような遷移が存在 F = {q1,q4} 例5.3: {wwR | w ∊ {0,1}*} のPDA start q1 ε,ε à $ q2 0,ε à 0 1,ε à 1 ε,ε à ε q4 ε,$ à ε q3 0,0 à ε 1,1 à ε 気持ち（w=1001111001 を例に）前半（10011）をスタックにプッシュ後半（11001）と一致するかを1記号ずつチェック PDA を M = （Q, Σ, Γ, δ, q0, F）とする Q = {q1,q2,q3,q4}, Σ = {0,1}, Γ = {0,1,$}, 1 1 0 0 1 $ スタックの変化 δ（q1,ε,ε） = {（q2,$）} δ（q2,0,ε） = {（q2,0）}, δ（q2,1,ε） = {（q2,1）}, δ（q2,ε,ε） = {（q3,ε）} δ（q3,0,0） = {（q3,ε）}, δ（q3,1,1） = {（q3,ε）}, δ（q3,ε,$） = {（q4,ε）} F = {q1,q4} 例5.4: {w ∊ {0,1}* | N0（w）=N1（w）} 気持ち start 0,$ à 0$ ε,ε à $ スタックの先頭が$ q1 1,$ à 1$ 入力が0なら，0をプッシュ， 0,0 à 00 q2 入力が1なら，1をプッシュ 1,0 à ε ε,$ à ε 1,1 à 11 スタックの先頭が0 q3 0,1 à ε 入力が0なら，0をプッシュ， ※「0,0 à 00」を入力が1なら，0をポップ「0,ε à 0」に変えてはダメスタックの先頭が1 系列1101000011 を入力したとき入力が1なら，1をプッシュ，のスタックの様子入力が0なら，1をポップ 1 1 0 1 1 1 1 1 0 0 0 $ $ $ $ $ $ $ $ $ $ $ 文脈自由言語とプッシュダウンオートマトン言語の関係文脈自由言語のクラスとプッシュダウンオートマトンで受理される言語のクラスは一致する { an bn cn | n >=0 } { an bn | n >=0 } チューリング機械で受理される言語のクラス文脈自由言語のクラス正規言語のクラス = プッシュダウンオートマトンで受理される言語のクラス練習問題練習問題12-2 次の言語を受理するプッシュダウンオートマトンを作成せよ（例5.2〜5.4のように状態遷移図を作成する） { 0 i1 j | 0 ≤ i ≤ j } { w ∊ {0,1,2}* | N0（w）=N1（w） } { ai bj ck | i = j または j=k となる非負整数 }