偶数の 1 で 0 で終わる文字列のセットを受け入れる決定論的有限オートマトンを作成する必要があります。このセットの文字列として 0 を含める必要がありますか? どうすればこれを行うことができますか？
質問する
1032 次
1 に答える
2
0このセットの文字列として含める必要がありますか?
はい
どうすればこれを行うことができますか？
有限オートマトンを構築するには、状態と遷移を識別する必要があります。Myhill-Nerode の定理により、「区別できない」文字列の等価クラスを特定できれば、有限オートマトンの必要な (そして十分な!) 状態を見つけることができます。
2 つの文字列xとyは、この意味で区別できません。他の文字列の場合、言語にとのz両方が含まれているか、どちらも含まれていないかのいずれかです。xzyz
あなたの場合、等価クラスを特定してみましょう。空の文字列は、同等のクラスにあります。空の文字列を言語に追加して文字列を取得できるため、文字列0は別の同等のクラスに0あります (言語で文字列を取得するために空の文字列に空の文字列を追加することはできません)。これまでに、空の文字列用と0. これらは両方とも、FA で異なる状態を必要とします。
文字列は1どうですか？言語の文字列をgetに0追加できるため、両方と空の文字列と区別できますが、言語の文字列を取得するためにまたは空の文字列に追加することはできません。したがって、さらに別の状態があります。1011100
文字列は00どうですか？この文字列は言語に含まれておらず、この文字列に他の文字列を追加して言語の文字列を取得することはできません。これは別の等価クラスです。次の文字列 、01、10もこのクラスにあることがわかります。
文字列11は、空の文字列と同じクラスになります。言語の任意の文字列を追加して、言語11の別の文字列を取得できます。長さ 3 のすべての文字列を試してみると、それらすべてがすでに上記のクラスのいずれかに分類されていることがわかり、その時点でチェックを停止できます。
したがって、4 つの状態が[-]あります。次に、トランジションを理解します。[0][1][00]
を取得した場合は0...に[-]行く必要があり、を取得した場合は に行く必要があります。残りは、正規の文字列に追加することで得られる文字列と、結果の文字列がどのクラスになるかを把握し、その状態に移動します。[0]1[1]
于 2012-10-17T23:47:46.450 に答える