交代有限オートマトンと拡張正則表現

スポンサーリンク

概要

論文の詳細を見る
交代性有限オートマトンは1981年Chandraらによって導入され、そこでは、n状態の交代性有限オートマトンは、高々2^<2n>状態の決定性有限オートマトンに変換できること、および少なくとも2^<2n>状態必要なn状態交代性有限オートマトンが存在することが示された。交代性有限オートマトンは、非決定性有限オートマトンを拡張し、各状態(または、状態遷移)に任意の論理関数を割り付けることができるようにしたものである。この拡張により、交代性有限オートマトンは、同じ言語でも、非決定性よりも少ない状態数で記述できる可能性がある。また、正則表現にいろいろな集合演算を追加して、拡張正則表現が定義されるが、交代性有限オートマトンはこのような拡張正則表現とも滑らかな対応がえられる。
社団法人電子情報通信学会の論文
1996-03-11

著者

関連論文

もっと見る

スポンサーリンク