木解析による特徴記号列集合からのオートマトン合成

概要

論文の詳細を見る
順序機械のミーリー形表現は、入出力を対にして考えると、決定性有限状態オートマトンの形式に変換出来る。そのような考えの上に立って、決定性有限状態オートマトンの動作を、入力記号列受理特性により代表して表現する、特徴記号列集合の作成方法を既に与えたが、それから元のオートマトンを復元する方法の確立には未だ至っていない。本研究は、この問題を取り上げ、次の2つの性質イ.特徴記号列から導出される特徴分類木の各状態間の推移性、ロ.特徴分類木に含まれる性質としての、各状態間の最終状態、あるいは受理されない状態への推移列集合の共有関係、即ち、推移の部分整合性を用い、特徴分類木を逆方向決定性オートマトンに2度変換することにより得られる、特徴分類木と等価なオートマトンの、各状態に付加される状態記号集合の共通状態記号(コンジャンクションを含む)、並びに、その共通記号間の部分整合性を考慮して、そのオートマトン簡約化し、最小状態の元のオートマトンを合成する方法を提案する
一般社団法人情報処理学会の論文
1993-03-01