交代有限オートマトンから他の有限オートマトンへの変換について

山本 博章  

誌名
電子情報通信学会論文誌 D   Vol.J82-D1   No.8   pp.971-979
発行日: 1999/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマトン理論,言語理論
キーワード: 
有限オートマトン,  交代有限オートマトン,  ε 動作,  論理関数,  

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


あらまし: 
本論文では,交代有限オートマトンと他の有限オートマトンとの変換アルゴリズムに 焦点を当て,いくつかのアルゴリズムを提案する.従来の研究は,主に,計算能力に 焦点が当てられ,変換アルゴリズムに関してはあまり議論されていない. 我々は,まず,交代有限オートマトンを非決定性,決定性などの有限オートマトンへ 変換するアルゴリズムを示す.このとき,非決定性を決定性へ変換するときに 用いられる 部分集合構成法を一般化し,論理関数構成法と呼ぶ手法を示す. 次に,我々は,入力を読まずに状態のみ 変化できる ε 動作を導入したモデルを定義し, これが ε 動作をもたない 同じ状態数の交代有限オートマトンへ変換可能であること, 及び ε 動作を除去するための具体的なアルゴリズムを示す.