一方がε-動作なし空スタック受理式である決定性プッシュダウン変換器の等価性判定

富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J62-D   No.7   pp.467-474
発行日: 1979/07/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
等価性判定の可解性が判明している決定性プッシュダウンオートマトン(DPDA)の部分クラス対の内,一方が一般(クラスD),もう一方がε-動作なし空スタック受理式(クラスR0)であるものは,ある系統において現在最大のものであるが,本論文においては,それら各々に出力機構を付与したような決定性プッシュダウン変換器(DPDT)に対しても,その両者の等価性判定が可解であることを明らかにした.ここで,2個のDPDTは,各々が同じ入力記号列集合を受理し,且つ共通の受理入力記号列に対して同じ出力記号列を出す場合に,両者は等価であるとする.ここでの等価性判定法は,空スタック受理式(クラスD0)のDPDAとクラスR0のDPDAとの等価性を判定するための分岐アルゴリズムを基礎としているが,その逐次的チェック段階において出力のずれの調整可能性を考え,更に,その結果入力部分に関しては同じであるが出力部分が異なっているような関係式(DPDTにおける関係式)の対が出現したときのため,その出力関係の両立性をチェックする過程を新たに設けている.