4

これは私の宿題です。

演習 3: 言語 L = { a^nb^m|の規則的な文法を見つけます。n + m は奇数}。入手方法を表示します。

質問は、私が答えを得る方法を示すように求めます. だからここに私の説明があります。

DFA を構築します DFAから、 S -> aA |を取得します。ba A -> aS | BS | nullしたがって、通常の文法は G = {V , T , S, P} です。ここで、V = {S, A} T = {a, b} P = {S -> aA | null bA、A -> aS | BS | ヌル}
DFA











ただし、次の質問は次のとおりです。

演習 3 の文法によって生成された言語を受け入れる DFA を構築します。可能であれば、構築された DFA を単純化します。

したがって、DFA を描画することは演習 3 の説明として期待されているものではないと思います。おそらく、DFA を描画せずに通常の言語を取得する別の方法があると思います。私にお知らせください。

ありがとうございました。

4

2 に答える 2

1

通常、DFAを導出することは、文法を導出することよりも困難です。もう 1 つは、最初に文法を構築することで、この文法に一致する最小限の DFA を生成できることです。DFA の構築から開始する場合は、対応する文法を派生させてから、この文法から最小限の DFA を派生させる必要があります。

DFA を導き出すのが難しい理由の例として、DFA が言語と一致しませんa^n b^m, n+m odd。a奇数の長さのすべての文字列に一致しbますababa。

対応する文法を作成しようとしました：

  S  -> 'a' L2
     -> 'b' B2

  L1 -> 'a' L2
     -> 'b' B2

  L2 -> 'a' L1
     -> 'b' B1

  B1 -> 'b' B2

  B2 -> \empty
     -> 'b' B1
  • S 開始記号です。
  • L1a then の奇数シーケンスを表しbます。
  • L2a then の偶数シーケンスを表しbます。
  • B1の奇数シーケンスを表しbます。
  • B2の偶数シーケンスを表しbます。

この文法は正則であり、DFA の構築に適しています。

于 2015-11-23T14:24:51.913 に答える