1

DFA の描画のコツをつかもうとしています。私は次の試みに関連して次の問題を抱えています。誰かが私が正しいかどうか、または間違っているかどうかを教えてくれるかどうか疑問に思っていました。ありがとう！また、これらの方法について詳しく学ぶための優れたリソースを誰かが持っている場合は、大歓迎です。

次の言語を認識する DFA の状態図を示してください。すべての部分で、アルファベットは {0,1 } です

{w | w の長さは最大 5}

ここに画像の説明を入力

4

3 に答える 3

1

ここにいくつかの手がかりがあります。

  • 「最大 5」: これは、数を数える必要があることを意味します。ステート マシンでは、カウントは各ノードのコンテキストによって実行されます。つまり、それぞれが特別な意味を持つ多数のノードが必要になり、その意味が「カウンター値」になります。
  • 「最大 5」: これは、長さ 0、1、2、3、4、および 5 の単語を受け入れなければならないことを意味します。
  • あなたのアルファベットは ですが、頻度、順序、またはおよび{0,1}に関連する言語の要件はありません。これは、 のトランジションが発生するたびに、 で同じトランジションを使用できる必要があることを意味します。逆も同様です。(または、この規則に還元される同等の関係 - ただし、これは考える必要がないため、括弧で囲まれています。)0101
于 2011-09-20T01:24:30.097 に答える
0

上記のDFAは間違っていると思います。長さ 5 までの文字列を受け入れるため、最初の 6 つの状態すべてを最終状態にする必要があります。「1」のみを受け入れていますが、「0」も受け入れる必要があります......したがって、すべて 1 に 0 を付けてください。

于 2011-09-20T01:25:17.597 に答える
0

エラーは次のとおりです。

  • マークされた開始状態はありません。
  • 文字列 "0"、"" (空の文字列)、"1" は拒否されますが、所定の言語の範囲内です。つまり、長さ 5 以下のすべての単語ではなく、正確に長さ 5の単語のみを受け入れているということです。

アルファベットは {0, 1} であるため、0 または 1 が検出されたときに何が起こるかを各状態で指定する必要があります。エッジが指定されていない入力文字に遭遇した場合、慣例により、デッド状態になります。この状態は、常にそれ自体に戻り、受け入れられず、描画されずに残されます。これが、一番右の状態が不要である理由ですが、左の状態は不完全です。

最後の重要なヒント: 複数の "Accept" または "Final" 状態を持つことができます。

于 2011-09-20T01:25:27.490 に答える