文脈自由言語の質問 (ポンピング補題)

Question

これがプログラミングに直接関係していないことはわかっていますが、ポンピング補題を次の証明に適用する方法を知っている人はいるかどうか疑問に思っていました。

それを見せてください L={(a^n)(b^n)(c^m) :n!=m} コンテキストフリー言語ではありません

私はポンピング補題の適用にはかなり自信がありますが、これには本当にイライラします。どう思いますか？

Answer 1

編集：私は完全にあなたを間違った道に導いていました。自分自身で問題を完全に解決していないときに手助けしようとすると、このようなことが起こります。

オグデンの補題

L が文脈自由であると仮定します。オグデンの補題により、次の特性を持つ整数 p が存在します。

L に少なくとも p シンボルの長さの文字列 w があり、これらのシンボルのうち少なくとも p が「マークされている」とすると、w は uvxyz として表すことができ、次の条件が満たされます。

1. x には少なくとも 1 つのマークされたシンボルがあり、
2. u と v の両方にマークされたシンボルがあるか、y と z の両方にマークされたシンボルがあるかのいずれかです。
3. vxy には最大 p 個のマークされたシンボルがあり、
4. うーん^私 ｘ ｙ^私 i >= 0 の場合、z は L にあります

それがオグデンの補題です。ここで、q を p 以下のすべての正の整数で割り切れる整数とします。w = a とします^p+q b^p+q c^p. 。cごとにマークを付けます。#2 により、u または v には少なくとも 1 つの c が含まれなければなりません。u または v のいずれかに他のシンボルが含まれている場合、#4 は失敗するため、u と v には c のみが含まれている必要があります。しかし、i = q/|uv| の場合、#4 は失敗します。Qは| uv |で割り切れることがわかっていますp> | uv | > 0、およびqはp未満のすべての正の整数によって分裂可能です。

すべてのシンボルをマークすると、オグデンの補題がポンピング補題に変わることに注意してください。

ポンピング補題

L が文脈自由であると仮定します。ポンピング補題により、L 内の任意の文字列 w を uvxyz として表すことができる長さ p (必ずしも上記と同じ p である必要はありません) が存在します。

1. | vxy | <= p、
2. | vy | > = 1、および
3. うーん^私 ｘ ｙ^私 i >= 0 の場合、z は L にあります。

L に文字列 w が与えられると、m > n または m < n のいずれかになります。p = 2 と仮定します。

m > n であるとします。(Λ は空の文字列を示すことに注意してください。)

• u = a としますⁿ bⁿ c^m-1
• v = c とします。
• x = Λ とします
• y = Λ とします
• z = Λ とします

n > m であるとします。

• u = a とします^n-1
• v = a とします
• x = Λ とします
• y = b とします
• z = b とします^n-1 c^メートル

これは、L が文脈自由言語 (文脈依存型であっても) であるという仮定に対して、ポンピング補題を使用した反例を提供する L の文字列がないことを示しています。