1

私はステートマシンを扱う宿題に取り組んでいます。私はそれらがどのように機能するかを理解していますが、私が理解していないこの特定の質問のいくつかの側面があります。

Let L be the set of strings over {a,b} ending with the substring abba.
a. Build a DFA that accepts L.
b. Build an NFA with 6 transitions that accepts L.

Lをステートマシンに組み込むにはどうすればよいですか？パートbで完全に迷子になっていますが、パートaを理解すれば、bはそれほど難しくないはずだと感じています。

4

2 に答える 2

2

少しバックアップしましょう。慣例により、「L」は「言語」を定義するために使用されます。このコンテキストでは、何らかの定義を満たす文字列のセット (おそらく無限) です。有限オートマトンで遊んでいるとき、どの文字列がマシンによって「受け入れられ」、どの文字列が「拒否」されたかに関心があります。一般に、特定の言語のすべての文字列を受け入れ、含まれていない文字列を拒否します (別の問題の見方は、言語をマシンが受け入れるすべての文字列のセットとして定義できるということです-それらは同等です）。

最初の質問は、L を受け入れる DFA を構築する演習です。つまり、"aaba" で終わる文字列はすべて受け入れ、"abba" で終わらない文字列は拒否します。あなたの混乱は、L が何らかの形であなたのマシンの「一部」であると考えることに起因しているようです。せいぜい、L の記述をマシンにエンコードするだけです。

2 番目の質問は、NFA で同じことを行うように求めていますが、遷移が 6 つしかないという追加の制限があります。

于 2012-06-23T01:32:13.233 に答える
0

これを試してみましょう：

Node 0:
a -> node 1   <-- This means, "if the next character is a, then go to node 1"
b -> node 0
END -> error
Node 1:
a -> node 1
b -> node 2
END -> error
Node 2:
a -> node 1
b -> node 3
END -> error
Node 3:
a -> node 4
b -> node 0
END -> error
Node 4:
END -> Success!
a -> node 1
b -> node 0

そうすべきだと思います。各ノードには、a、b、または文字列の終わり (END) の 3 つの可能な矢印があります。「abbaEND」の一部である各入力は次のノードにつながり、最終的に成功します。「abbaEND」の一部ではない各入力は、適切なノードに戻ります。基本的に、a の場合は別の「abba」ブロックの開始として扱い、ab の場合は「abba」が次に来ると想定します。早期の END は失敗です。それが DFA マップになります。

したがって、a と b の任意の文字列を入力として使用すると...この DFA は、Success! でのみ終了する必要があります。文字列が「abba」で終わる場合、他の文字列ではエラーで終わるはずです。

于 2012-06-23T01:41:14.157 に答える