準拡張正規表現に対する新しい有限オートマトンモデルについて

山本 博章  

誌名
電子情報通信学会論文誌 D   Vol.J86-D1   No.7   pp.443-451
発行日: 2003/07/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマトン理論,言語理論
キーワード: 
準拡張正規表現,  交代有限オートマトン,  同期,  

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


あらまし: 
準拡張正規表現とは,共通集合演算をもつ正規表現である.長さ m の正規表現は,たかだか 2 m 状態の非決定性有限オートマトンに変換できることが知られているが,準拡張正規表現をNFAに変換しようとすると,共通集合演算のため,状態数が指数的に増加してしまう.本論文では,部分入力同期式交代有限オートマトンと呼ばれる新しいモデルを提案し,長さ m の準拡張正規表現はたかだか 2 m 状態の部分入力同期式交代有限オートマトンに変換できることを示す.この結果の応用としては,Yamamotoによる準拡張正規表現の所属問題への適用がある.