各状態に一意の入力/出力シーケンスがあるかどうかを調べるにはどうすればよいですか? 標準化された技術や方法はありますか? オンラインで何も見つからないようです。
助けてくれてありがとう！
1 に答える
1
決定論的 FSM (つまり、イプシロン状態遷移のないもの) の場合、次の条件が満たされた場合にのみ、状態につながる一意の入力シーケンスがあります。
1) 状態へのパスが存在する必要があります。(孤立した到達不能状態は資格を得ることができませんでした)。
2) 開始状態に戻るパスはありません (そうでない場合、ターゲット状態への直接行軍が到達し、開始状態に戻ってから直接行軍を行う行進も機能します)。
3) 各状態 S について、S からターゲット状態に到達できないか、Sがターゲット状態であるか、開始状態から S への一意のパスがあり、S からターゲット状態への一意のパスがあります。
有向グラフ オブジェクト表現を使用していると仮定すると、これは、グラフ内に開始状態で終了するエッジがなく、グラフ内の各状態 S についても、S からターゲットへのパスがないことを意味します。またはユニークなものがあります。
コードでこれを見つけようとしている場合は、おそらく修正されたダイクストラのアルゴリズムを使用してこれに対処できます。
これは、一意の入力シーケンスを持つことのみを扱うことに注意してください。実際には、同じ出力シーケンスを生成する入力シーケンスが複数存在する可能性があるため、一意の出力シーケンスを持つには、より注意が必要です。ただし、考え方は同じですが、3 番目の基準を変更する必要があります。
3) 各状態 S について、S からターゲット状態に到達できないか、Sがターゲット状態であるか、または S と T の両方がターゲット状態へのパスを持っている場合、それらは同じ出力シーケンスを生成する必要があり、出力シーケンスは開始状態から S まで生成される出力シーケンスと、開始状態から T まで生成される出力シーケンスは同じでなければなりません。
繰り返しますが、変更された Dijkstra がおそらく最善の策です。
于 2014-12-30T21:59:40.140 に答える