0

AとBを受け入れるある種の文字列を受け入れるFAを設計することを楽しみにしています。

まず、A の数が B の 5 倍多い弦。

つまり L={w∈{A,B}* and (nA(W)-nB(W) mod 5=0)

また、文字列内の異なる数の文字を受け入れる FA:

L={A^n B^m C^k | n,k>0 and m>3}

いくつかの FA を設計しましたが、この複雑な弦では完全に機能しませんでした。

これをどのように設計すればよいですか？

4

1 に答える 1

1

残念ながら、英語のテキストが数式と一致しないため、あなたの質問は混乱を招きます. 次に、これら4つの質問に答えようとします。

  • a (= #a(w)) の数が b の数 ( #b(w)) の 5 倍である {a,b} 上の文字列からなる言語、 L = { w in {a,b}* : #a(w)>#b(w) and #a(w)=#b(w)mod5 }

    これは、NFA では実行できません。証明は、文字列 a^pb^5p でポンピング補題 (PL) を使用することで簡単になります。ここで、p は PL の定数です。

  • L={w∈{A,B}* : (nA(W)-nB(W)) mod 5=0}あなたが書いた language: については、5 つの状態のサイクルで構成される DFA で実行できます。

    トランジションは、a を読んだら時計回り、b を読んだら反時計回りです。ランダムに 1 つの状態を初期状態として選択し、同じ状態を最終状態とします。

  • 言語 L={A^n B^m C^k | n,k>0 and m>3}、L を次のように読めば簡単に見つけられるはずです。L=A(A)* B(B)* c^4(C)*

  • 文字列内の異なる数の文字を受け入れる言語の場合 (a、b としましょう)。言語はR={ w in {a,b}* : #a(w) not equal #b(w)}

    この言語も、NFA では認識できません。この言語が通常の (NFA によって認識される) 場合、次の言語になります。

    L=a*b* intersection (R complement). 言語 L は{a^n b^n/ n non-negative integer}.

    言語 L は、非正規の言語について述べているほとんどの本の最初の例です。

うまくいけば、この回答がお役に立てば幸いです。

于 2014-07-11T00:55:00.020 に答える