次の言語は文脈自由ですか?
L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0}
これを生成するために文脈自由文法を考え出そうとしましたが、できないので、文脈自由ではないと仮定しています。矛盾による私の証明については：
L が文脈自由であると仮定すると、
ポンピング補題によって与えられる定数を p とします。
文字列 S = a^pb^pc^pd^p を選択します。ここで、S = uvwxy
|vwx|として <= p の場合、最大で vwx に 2 つの異なるシンボルを含めることができます。
ケース a) vwx には 1 つのタイプのシンボルのみが含まれているため、uv^2wx^2y は i+s != k+r になります。
ケース b) vwx には 2 種類のシンボルが含まれています。
i) vwx は b と c で構成されているため、uv^2wx^2y は i+s != k+r になります。
ここで私の問題は、vwx が a と b、または c と d のいずれかで構成されている場合、i と k または s と r が一斉に増加して i+s == k になる可能性があるため、それらをポンピングしても言語が壊れる必要はないということです。 +r。
私は何か間違ったことをしていますか、それともこれは文脈自由言語ですか?