決定性プッシュダウンオートマトンの等価性判定が可解であるためのある十分条件

富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J64-D   No.1   pp.9-16
発行日: 1981/01/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(684.8KB)>>
論文を購入




あらまし: 
一方が(空スタック受理式)決定性プッシュダウンオートマトン(DPDA)M1で,もう一方が実時間空スタック受理式DPDAM2である場合に対する等価性判定の可解性は,大山口らにより初めて明らかにされたが,同判定に関しては,その後より単純で直接的な分岐アルゴリズムも与えられた.ここで,そのアルゴリズムにおける有限終端性の基本の一つとなっていたのは,次のような性質である.すなわち,〔命題〕“M1M2各々からの計算状態(pAα″),(β)が等価であるとき,プッシュダウン記号列Aα″の上端1記号Aをポップアップするような任意の推移に対し,それと同じ入力記号列による(β)からの推移において影響を受けるβの部分は,最上部から有限の範囲に限られる.”ところで,この性質が成立するために,M2の実時間性は必要条件とはなっていない.そこで本論文においては,このような性質の成立性を条件とするだけで,両者の等価性判定が可能となることを明らかにする.その具体的判定法は,前記の分岐アルゴリズムを拡張したものとして与える.これにより,決定性文脈自由言語の等価性判定の可解性は,冒頭の結果よりも真に拡張される.