computer-science - ファイルが与えられた場合、ファイルに存在する単語のみを受け入れる NFA を生成する方法は?

Question

任意のドキュメントが与えられた場合、ドキュメントに含まれる単語のみを受け入れる NFA を生成できるようにしたいと考えています。基本的に、任意のドキュメントから動的に NFA を生成できる関数を書きたいと考えています。すでにそれを行う既存のアルゴリズムはありますか?

Answer 1

必要なものが要件のない NFA だけである場合、構築はほとんど簡単です。

単語 w ごとに、|w| を使用して NFA に個別の分岐を作成します。+ 1 状態 (初期状態を除く)。開始状態から最初の状態に空の遷移を追加し、次に w の n 番目の文字で n 番目の状態から n+1 番目の状態への遷移を追加します。|w|+1 番目の状態を受け入れるようにします。

これにより、ファイル内のシンボル + 単語と同じ数の状態を持つ DFA が得られます。より少ない状態が必要な場合は、すべての単語のすべての最初の文字に対して最初の「レイヤー」を作成し、すべての単語のすべての 2 番目の文字に対して 2 番目の「レイヤー」を作成するなどして、よりレイヤー化された何かを実行し、レイヤーの状態からの遷移を追加できます。遷移を有効にする単語 w がある場合、n から層 n+1 の状態へ。実際、これを正しく行えば、最終的に DFA になり、それも最小限になる可能性があります (演習: これを証明または反証してください)。