theory - 文脈自由言語の質問（反復補題）

Question

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

L = {（a ^ n）（b ^ n）（c ^ m）：n！=m}が文脈自由言語ではないことを示す

私はポンピング補題を適用することにかなり自信がありますが、これは本当に私を苛立たせています。どう思いますか？

Answer 1

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

オグデンの補題

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

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

1. xには、少なくとも1つのマークされた記号があります。
2. uとvの両方に記号が付いているか、yとzの両方に記号が付いています。
3. vxyには最大でp個のマークされた記号があり、
4. uv ⁱ xyizはLでⁱ >=0

それがオグデンの補題です。ここで、qをp以下のすべての正の整数で割り切れる整数とします。w = a ^{p + q} b ^{p + qcp}とします。すべてのcをマークします。＃2までに、uまたはvには少なくとも1つのcが含まれている必要があります。uまたはvのいずれかに他の記号が含まれている場合、＃4は失敗するため、uとvにはcのみが含まれている必要があります。しかし、i = q / | uv |の場合、＃4は失敗します。qは|uv|で割り切れることがわかっています なぜならp>|uv | > 0であり、qはp未満のすべての正の整数で割り切れます。

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

補題のポンピング

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

1. | vxy | <= p、
2. | vy | > = 1、および
3. uv ⁱ xy ⁱ zは、i>=0の場合はLになります。

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

m>nであると仮定します。（Λは空の文字列を表すことに注意してください。）

• u = a ⁿ b ^{ncm -1とし}ます
• v=cとします
• x=Λとします
• y=Λとします
• z=Λとします

n>mであると仮定します。

• u = ^{an-1とします}
• v=aとします
• x=Λとします
• y=bとします
• z = b n ^{- 1cmとします}

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