諸受理方式による決定性カウンタの言語クラスについて

概要

論文の詳細を見る
決定性プッシュダウンオートマトンにおける受理方式は主に4つある。空記号列による推移を許す言語クラスにおいては、本質的にその言語受理能力が受理方式によらずに同じである言語クラスが多い。しかし、それは終止記号や、スタック記号の種類を増やすことにより同等の性質を有することで証明されている。従って、終止記号が導入不可能であり、スタック記号の種類を増やすことができないような言語クラスにおいて、受理方式の違いにより言語受理能力がどのように異なるのかは、興味深いところである。本文においては、スタック記号が1種類である決定性カウンタにおいて、受理方式により言語受理能力が明らかに違うことを論ずる。決定性カウンタにおいては、スッタクの種類が1種類という制限により、スタック記号の種類を増やすことができない。従って、受理方式によっては終止記号を使用できず、受理方式により言語クラスが違うことが予想される。すでに、非決定性カウンタに関しては受理方式により言語クラスが異なる事が言及されている。そこで、決定性カウンタにおいては受理方式によりどのように言語クラスが変わるかを論ずる。特に、最終状態受理式決定性カウンタの言語クラスと空スタック受理式決定性カウンタの言語クラスの共通部分が正規言語クラスと本質的に等しいことは興味深いことである。
一般社団法人情報処理学会の論文
1996-03-06

諸受理方式による決定性カウンタの言語クラスについて

スポンサーリンク

概要

著者

関連論文

スポンサーリンク