context-free-grammar - 文脈自由言語で補題をポンピングする

Question

A = {0^a 1^b 2^c | a < b < c}

A が文脈自由でないことを示す必要があります。これには Pumping Lemma を使用する必要があると思いますが、どうすればよいでしょうか?

Answer 1

目標は、長さが最小ポンピング長さ以上のストリングの場合、ストリングをポンピングできないことを証明することです。つまり、それを部分文字列uvxyzに分割すると、のコピーを作成した（またはコピーを削除した）結果として得られる文字列はv、yまだ言語のままですA。

言語の1つの文字列をポンピングできないことを示す必要があるだけであることに注意してください（最小ポンピング長pを満たす限り）

この言語とそれがどのように関連しているかを考えてくださいA：

Answer 2

ステップ 1: 最小ポンピング長 (2^p+1) を計算します。p は変数の数です。ステップ 2: その長さのストリングをいくつか作成します。ステップ 3: |wy|> 0 (|x| は 0 になる可能性があることに注意) および |wxy| となるように、文字列を vwxyz に分割し始めます。<= 2^p+1。w と y を定義するさまざまな方法と、それらの部分文字列を同じ場所で繰り返し始めるとどうなるかを見てください。

鍵はおそらく0と1の境界線にあるでしょう。