math - 文脈自由言語による補題のポンピング

Question

私は{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 、m文字列が

   z = a^m b^(m-1) c^(m-2)

次に、文字列が空にならない(z =) uvwxyように分割され 、「」を選択すると混乱します。私が選ぶとしたら、私が持っているとしましょう： そして、私には言語にあるvwxを選ぶことができるように見えるので、そこからどこへ行くべきか完全にはわかりません。vx#(vwx)<=mii=1uv^1wx^1y

助言がありますか？

Answer 1

少し良い z = a^(m+2)b^(m+1)c^(m) を選ぶことから始めます。ここで、m はポンピング長です。この文字列は明らかに言語であり、その長さは m 以上です。したがって、言語が CFL であると仮定すると、ポンピング補題が適用されます。さて、あなたはそれを知っているので |vwx| <= m およびその |vx| > 0 の場合、vwx は (1) a のみ、(2) 一部の a と一部の b、(3) b のみ、(4) 一部の b と一部の c、または (5) c のみで構成される必要があることもわかっています。

ケースごとに個別に対処します。最初の 2 つのケースを担当します。

ケース 1: これは補題が |vx| > 0. ここで、i = 0 を取るとします。補題は、z' = uv^(0)wx^(0)y は依然としてその言語に属していることを示しています。ただし、z' は a^(m+2-s)b^(m+1)c^(m) の形式であり、s > 0 であるため、a の数が厳密にb の数。したがって、z' は言語に含まれておらず、この場合はポンプに失敗します。

ケース 2: これは、s+t > 0 となる s,t に対して、vx が a^(s)b^(t) であることを意味します。ここでも、i = 0 とします。その場合、z' は a^ の形式になります。 (m+2-s)b^(m+1-t)c^(m)。t が正の場合、b の数が厳密に c の数よりも大きいという条件に違反しています。t がゼロの場合、s は正でなければならず、その場合はケース 1 に退化します。したがって、z' は言語に含まれず、このケースはポンプに失敗します。

他のケースに対処するには、それぞれに異なるポンピング指数 i を選択できることを覚えておいてください。

編集: (この質問に関する過去の議論から、他の 3 つのケースを表示することにしました。)

ケース 3: これは、いくつかの s > 0 に対して vx が b^(s) であることを意味します。メートル）。s は正であるため、これは b の数が c の数より厳密に大きいという条件に違反します。したがって、z' は言語に含まれておらず、この場合はポンプに失敗します。(このケースがポンピングに失敗したことを示すために、i を 1 以外に等しくすることもできます。)

ケース 4: これは、s+t > 0 となる s,t に対して vx が b^(s)c^(t) であることを意味します。 b^(m+1+s)c^(m+t)。s が非ゼロの場合、a の数が厳密に b の数よりも大きいという条件に違反しています。s がゼロの場合、t は非ゼロでなければならず、その場合、b の数が厳密に c の数よりも大きいという条件に違反します。したがって、z' は言語に含まれておらず、この場合もポンプに失敗します。

ケース 5: これは、いくつかの s > 0 に対して vx が c^(s) であることを意味します。 s)。s は正であるため、b の数が c の数より厳密に大きいという条件に違反しています。したがって、z' は言語に含まれておらず、この場合はポンプに失敗します。

5 つのケースすべてがポンピングに失敗するため、ポンピング補題は、この言語が文脈自由ではないことを示しています。

Answer 2

注：コメントを少し行ったり来たりした後、私が間違っていることがわかり、ウィリアムの答えは実際には正しいです。この回答はここに残しておきますので、私の推論のどこが失敗したかを指摘できます。

私は次のように考えます。

ポンピング後に言語定義内にとどまる可能性さえあるために、部分文字列 v、w、x が持たなければならないプロパティは何ですか? v も x も、"ab" や "bc" のような部分文字列を含むことはできません。さもないと、入力言語からすぐに送り出されます。したがって、v と x はそれぞれ、空、すべて a、すべて b、またはすべて c でなければなりません。

言語にある文字列 aaabbc を考えてみましょう。

u="aa", v = "a", w = イプシロン, x = "b", y = "bc"; を選択するとどうなるでしょうか。そしてvとxをポンプしますか？(これが私の間違いです: v と x が実際に文字列から削除される n=0 のケースを考慮しませんでした; どのように uvwxy を選択しても、n=0 または n>1 のいずれかのケースでは証明が失敗します。 uvwxy は uv ⁿ wx ⁿ y にポンピングされます)。

注: CFL ポンピング補題は、言語が文脈自由でないことを証明するために使用できますが、ポンピング補題自体に従うだけでは、言語が文脈自由であることを示すには不十分 です。CF でない言語もありますが、CFL ポンピング補題のすべての条件は依然として保持されます。そのような場合は、もう少し強力なテストであるOgden の補題を調べて、それを使用して言語が CF ではないことを示すことができるかどうかを確認することをお勧めします。

Answer 3

ポンピング補題は、言語が文脈自由である場合、「ポンピング」することを示しています。つまり、文脈自由であれば、次のようになります。

長さ p 以上の任意の文字列 s を s=uvxyz に書き換えることができるように、最小の長さ p があります。ここで、u と y の項は任意の回数 (0 を含む) 繰り返すことができます。

典型的な用途は、言語が文脈自由ではないことを証明するために、言語がポンピングしないことを示すことです。あなたの仕事から、これがあなたがやろうとしていることのように見えます。

しかし、ポンピング補題の逆は誤りです: ポンピングはするが文脈自由ではない言語があります。実際、あなたの言語はそのような獣です。言い換えれば、あなたの言語は文脈自由ではありませんが、ポンピングします。(これを証明する最も簡単な方法は、 v="a" および y="b" となるように s を分割することです。) したがって、ポンピング補題は、この言語の分析にはあまり役に立ちません。代わりに、 Ogden の補題を検討することをお勧めします。