スタックの高さの特徴付けによる言語が決定性文脈自由でないことの証明言語が決定性プッシュダウン機械で受理できない原因を一部解明！ M M M M M { # , # # | M 1} が決定性文脈自由言語でないことが，次のように示せる． M M # を読み終わった段階でのスタックは殆ど空である． M M の情報がスタックに残っていないので # を検査できない．上里友弥 U発表者V 南出靖彦単純な入力の生成するスタックの周期性 + 入力が文字列 r の繰り返し r であるときには，以下のどちらかの，分かりやすい計算の構造があらわれる： R スタックの高さは常に Cr 以下である； Cw k または，スタックの内容に周期性が生じ ↵ ⇤ となる． Uこの言語が決定性文脈自由でないこと自体は既に知られている (R- k)． V 決定性プッシュダウンオートマトン U.S.V の復習 .S.(j) = プッシュダウンオートマトン + 決定性 = 有限オートマトン + 状態 + 決定性状態とスタックトップの記号が，遷移の種類（" Q` ({"} (⌃ :Z⇥ U昔から知られている性質であることがわかったので，再発見をしたに過ぎない (R)．V ⌃）を決定する． Z ⇥ [SPS]) ] Z ⇥ [SPS, GP*G, Sla>( )]) M はスタック全体で表現される直前の結果から以下のことが分かる： #M とのマッチングのためには ↵ 部まで TQT すると思われるが，これは実際に以下の形で証明される：定理 U下図も参照V 文字列 r を受理 , r を読んだあとに受理状態6 (✓ Z) に入る． .*6G の例 { M #M | M 1} , { M #K / + K , M #K 2 + M | M, K .*6G ではない例 { M #M + M | M 1} , 1}X r | r 2 {, #} , r は回文 X ⇤ 入力テープの R 方向性とスタックの揮発性に基づく直感 K #M について K = M を検査するには， K R （相当の情報）を Tmb? し， M k TQT しつつ # とのマッチングを行うと思われる． t, v を空でない文字列とする．任意の自然数 M について M M M 2 M M t , t v, t v , . . . は受理されないが，t v は受理される M ならば，v を読んでいる間にスタックの高さが定数 Ht,v 以下になる． M （スタック全体での表現を丁度 R つ分持っていることが本質で，スタックの内容を補助テープとして持つようなチューリング機械によるマッチングを考えても，同様の結果が示される．）マッチングするとスタックは殆ど空になるスタックの高さが H 以下となるタイミングも分かる．すなわち，受理状態に入る R 文字前には高さが H 以下になることが示せる：結果として，受理時点のスタックは殆ど空になっているはずである．実際に以下が成立する：定理 t, v を空でない文字列とする．任意の自然数 M について M M M 2 M M t , t v, t v , . . . は受理されないが，t v は受理される受理! H （マッチングを行っている，個数を比較している）ならば，t 系 M M R M M v 受理時点のスタックの高さが定数 Ht,v 以下になる． M M M { # , # # | M 1} を受理する .S. が存在したとすると， M M # 受理時点のスタックの高さが定数 H,# 以下となる．したがって，受理時点のスタックの高さは高々 H+R 程度になる． M M 巨大な M について H+R は無視でき， # を受理した時点で：スタックが殆ど空になっていることが分かった．すなわち，スタックには M の情報が残っていないことが分かった． "B#HBQ;`T?v (R) a2vKQm` :BMb#m`; M/ a?2BH :`2B#+?X .2i2`KBMBbiB+ +QMi2ti 7`22 HM;m;2bX AM7Q`KiBQM M/ *QMi`QH- NUeV,eky Ĝ e93- RNeeX (k) JXƘX >``BbQMX AMi`Q/m+iBQM iQ 6Q`KH GM;m;2 h?2Q`vX //BbQM@q2bH2v GQM;KM Sm#HBb?BM; *QX- AM+X- RNd3X (j) CQ?MƘ1X >QT+`Q7i M/ C2z`2vƘ.X lHHKMX AMi`Q/m+iBQM iQ miQKi h?2Q`v- GM;m;2b M/ *QKTmiiBQMX //BbQM@q2bH2v- RNdNX