1

nfa から dfa に変換すると、下の画像のような結果になる場合があります...私の質問は、状態 {4} からゼロ状態になることを記述する必要があるかどうかです。{4} の入力記号 1 を表示しないと、右下の図と同じですか? それともいいえ?

ここに画像の説明を入力

4

3 に答える 3

2

それは慣例の問題です。個人的には、DFA を不必要な状態で乱雑にしないことを好みます。特に、NFA からの変換によって取得された DFA はとにかく非常に複雑になる傾向があり、決定論的であるため、表示されていない遷移は無効でなければならないことがわかっています。

しかし、学界の多くの人々が他の規則を教えたり使用したりしており、すべての遷移を明示的に示す必要があることを私は経験しました。TA(チューター)として働いていたとき、私は実際にこれについて教授と話し合ったことがあります.彼は私たちチューターにDFAのトランジションの欠落の最終テストで減点することを望んでいました.

于 2012-06-04T21:19:42.953 に答える
1

{4}-> 0 遷移を記述する必要はありません。オートマットは既に単語を受け入れているからです。この移行は、これがソリューションにとって意味のある「何もない」ことを意味するだけです。しかし、詳細については、オートマトン全体を表示するために、それを与えると便利です。

于 2012-06-04T21:11:30.813 に答える
0

MinimalFA (MFA) を描画しようとしている場合にのみ重要です。
実際には、単一の NFA から無数の DFA を生成できます。それぞれの状態数は異なります。図の「Dead States」
を削除すると、MFA が得られます。DFA だけが必要な場合は図で問題ありません

于 2013-07-18T15:48:05.123 に答える