3

ポンピング補題について読み始めたばかりで、主に矛盾によって、いくつかの証明を実行する方法を知っています。私が答えを見つけられないように見えるのは、この特定の質問だけです。どうやって始めたらいいのかわからない。ポンピング長が必要であり、LPのすべての要素に対して. そしてもちろん、ポンピング補題の 3 つの通常条件と同じように w を書くことができます。wLENGTH(w) >= Pxyz

次の言語が非規則的であることを証明する必要があります。

L = {x + y = z | x,y,z element of {0,1}* and #(x) + #(y) = #(z) }

この種の質問を証明するプロセスを本当にマスターしたいのですが、誰かがこれについて私を助けてくれますか?

編集：申し訳ありませんが、アルファベットは文字列のバイナリ値を意味すること
を忘れていました。と のように。{0,1,+,=}##(00101) = 5#(110) = 6

4

2 に答える 2

2

プロセスをマスターしたいので、証明を示す前にいくつかのことを指摘します。

  1. 最初に注意することは、+とが=それぞれ1回だけ表示される可能性があることです。したがって、文字列wをw = abc、と書くと、ポンピングされた部分、、bを含めることができない+か、=さもなければ些細な矛盾に達する可能性があります（の定義とのw = xyz混同を避けるために、より標準的な表記法を使用していません）。L

  2. wもう1つの注意点は、通常、ポンピングする特定のストリングを選択することです。この場合、特定のプロパティを共有する文字列のクラスを選択する方が簡単な場合があります。ポンピングの補題は、1つのストリングを使用して矛盾に到達することだけを要求しますが、複数のストリングを使用して矛盾に到達できない理由はありません。

証明（スポイラー内）：

したがって、先頭の'を含まないようなw任意の文字列とします。ポンピング補題によって、次のように書くことができます。ポンピング補題によって、空ではないことがわかります。またはを含めることはできないため、またはのいずれかに完全に含まれます。任意のi≠1でポンピングすると、2進方程式が成り立たなくなります。これは、そのうちの1つが異なる数になるためです（これが、先頭のビットが必要ない理由です）。L|w| ≥ Px, y, z0ww = abcbb+=x, y,zwx, y, z0

于 2013-03-14T15:50:21.063 に答える
2

文字列として選択します1(0^n+1) + 1(0^n) = 11(0^n)。

言い換えれば、文字列は「2 の n+2 乗と 2 の n+1 乗の合計は 11 に等しく、その後に n 個のゼロが続く」と表示されます。

ポンピングされる文字列は完全に最初の加数の記号で構成されるため、ポンピングは表現される数値を変更する必要があります (数値に数字を追加または削除すると、数値が変更されます。これは、文字列に先行ゼロが含まれていないためです)。x + y = z成立し、その後成立x' + y = zしない場合x' != x(少なくとも整数以上)。

ポンピング補題では、ポンピングされた文字列が言語内にある必要があり、この文字列のポンピングが失敗するため、言語は規則的ではありません。

于 2013-03-14T16:51:33.920 に答える