正規表現からコンパクトなオートマトンを構成するための一手法

スポンサーリンク

概要

論文の詳細を見る
正規表現から構成されるコンパクトな非決定性有限オートマトンとしてfollowオートマトンやequationオートマトンというものが知られている.本論文は,equationオートマトンを構成するための手法として,Thompsonオートマトンから作成するためのアルゴリズムを与える.本アルゴリズムは,正規表現の長さをmとしたとき,O(m^2)時間で走る.また,正規表現に現れるアルファベット記号の数をsとしたとき,構成されるequationオートマトンは,状態数が高々s+1,状態遷移の数が高々s(s+1)となる.さらに,followオートマトンと組み合わせることによりさらにコンパクトな有限オートマトンを得ることができることを示す.
2010-09-22

著者

関連論文

もっと見る

スポンサーリンク