著者

上里 友弥 南出 靖彦

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.7, no.4, pp.8-20, 2014-08-29

---

本論では,言語が決定性文脈自由言語(DCFL)ではないことを証明するための,決定性プッシュダウンオートマトン(DPDA)に基づく手法を提案する.提案する手法は,計算中でのスタックの高さを特徴付けるもので,以下のようなスタックの変化に対する直感を形式的に扱うことができる:言語{anbncn | n ≧ 1}が何らかのDPDAで受理できたとすると,aの個数とbの個数を比較した結果として,anbnの部分を読み終わった段階のスタックはほとんど空になっているはずである.このとき,続く文字列cnを検査することができない.したがって,この言語はDCFLではない.具体的には,十分に長い繰返し文字列を消費した結果のスタックの内容には繰返し構造があることを示し,繰返し文字列を消費した結果のスタックが一般化順序機械と呼ばれる機械で定義可能であることを示した.この結果を用いて,上の例のようにaの個数とbの個数を比較するためには,スタックがほとんど空にならなければならないことを形式化して示した.