ファイルに存在する単語だけを受け入れるNFAを生成する方法をファイルに指定しますか？

Question

文書があれば、その文書にある単語だけを受け入れるNFAを生成できるようにしたい。 基本的には、どのドキュメントからでもNFAを動的に生成できる関数を作成したいと考えています。 既存のアルゴリズムがありますか？

Answer 1

必要なものがすべてNFAであれば、構成はほとんど自明です。

各単語wに対して、| w |を使用してNFAに異なる分岐を作成します。 + 1状態（初期状態を含まない）。開始状態から、最初の状態に空の遷移を追加し、w番目のn番目の状態のn番目の状態からn + 1番目の状態への遷移を追加します。 | w | + 1番目の状態を受け入れます。

これは、シンボル+単語がファイル内にある状態と同数の状態のDFAを提供します。状態の数を減らしたい場合は、すべての単語の最初の文字の最初の「レイヤー」、すべての単語の2番目のすべての文字の2番目の「レイヤー」などを作成し、レイヤーの状態からのトランジションを追加することで、遷移を有効にするワードwがある場合には、層n + 1の状態にnを加える。実際、あなたがこれを正しく行うならば、DFAで終わるでしょうし、それはおそらく最小限になるでしょう（練習：これを証明するか、それとも反証するか）。