0

次の言語の文法を教えてください{0^n w 1^n | n>=0 w is in {0,1}* and |w|=n}

解決策の試み:

S--> 0S1|R

R--> 0R|1R|empty

r の長さが 0 または 1 の数と同じであることを保証する方法がわかりません。

4

1 に答える 1

2

ここでは何も行きません。

すべての単語は、0^nw 1^n のようになります。したがって、ルール S -> 0S1 がある場合、これから生成できるすべての文形が 0^n S 0^n のように見える状態に到達します。

うーん...これは私たちが望んでいるものではありません。ではない？

さらに一歩進んで、ルール V -> 0|1 に関与する変数 V が必要です (編集: これが「目標」でしたが、問題が発生する可能性があるため、これら 2 つのルールは使用しません)これにより、S-> 0S1 の代わりに S -> 0SV1 を使用できるようになります。変化は何ですか？

これで、0^n S (V1)^n のようなセンテンシャル フォームが得られます。したがって、たとえば 000SV1V1V1 はそのようなセンテンシャル形式になります。今間違いなく必要なマイナーな追加の 1 つは、ルール S -> empty です。

まだ完全ではありませんが、最終的には 0^nV^n1^n のように見えるようにしたいと考えています。そこで、V と 1 を交換するルールを追加します。そのため、1V -> V1 を一連のルールに追加します。現在、どのような可能性がありますか？000SV1V1V1 のようなセンテンシャル フォームを指定すると、すべての V を左に、すべての 1 を右に移動できます。

そして今、私たちは本当の文法ナチになります。何も問題が発生しないようにしたいので、いくつかの小さな変更を加えます。私たちは少しスウィッピディ・スワッピディをします。これまでに発生したすべての S を T に置き換えます。そのため、S -> 0SV1 は 0TV1 などになります。また、ルール S -> empty|T を追加し、ルール T -> empty を削除します。これから何を得るのですか？ええと... 一見何もありません。しかし、今では、V を 1 と 0 に変えても問題が起こらないことを保証するメカニズムを構築できます。

TV -> C と CV -> CC というルールを追加するだけです。ああ、イエス・キリスト、これらすべての規則。

ここで、0^n TV^n 1^n という文形が与えられた場合、それをゆっくりと 0^n C^n 1^n に変換できます。使用は何ですか？すべての V を左に押していなければ、何も問題はありません。したがって、0000CCC1V111 のような文形は、C の隣にない限り V については何もできないため、私たちの目的に害を及ぼすことはありません。また、C をプッシュする可能性はありません。また、ルール C -> 0|1 を追加するので、途中で 1 と 0 に変更すると、まだ V が浮かんでいると単語を完成させることができません。

これはまったく必要ないかもしれませんが、それについてはわかりませんが、作成できるすべての単語が、この文法で指定したい単語のセットに含まれていることは、証明の一部です。ルールは次のとおりです。

S -> empty | T
T -> 0TV1
1V -> V1
TV -> C
CV -> CC
C -> 0|1

編集: ただし、これは Type-0 Grammer です。ただし、いくつかの変更により、これは同等の CSG になる可能性があります。

S -> empty | T
T -> 0TV1 | 0C1
1V -> V1
CV -> CC
C -> 0 | 1

主な違いは、ある時点で、0TV1 を文形式に追加するのをやめて、代わりに 0C1 で終了し、0^n C1 (V1) ^ (n-1) のような形式を取得できることです。また、すべての C を時期尚早に 0 と 1 に変換すると、すべての V を削除する可能性が失われます。したがって、これにより、探しているセットも生成されるはずです。

これは、stackoverflow に関する私の最初の回答でもあります。私はコンピューター サイエンスの理論が好きなので、私の説明が間違っていないことを願っています。もしそうなら、教えてください。

于 2015-11-06T18:19:38.043 に答える