私の質問は：
L = {x in {a,b}* | x は a と b の数が等しい}
文法を作成できるので、これが文脈自由言語であることはわかっています (e はイプシロン):
S -> aX | bY | e
X -> bS | aXX
Y -> aS | bYY
通常の言語と交差する文脈自由言語は文脈自由であるという事実を使用して、それが文脈自由であることを証明することもできます。
これは文脈自由言語であるため、CFL のポンピング レンマによれば、ポンピング長 p よりも長い任意の文字列をポンピングできるはずです。ただし、文字列 s = a^pb^pa^pb^p を選択した場合、この文字列はポンピングできないため、言語は文脈自由であってはなりません。
どこが間違っていますか？
確かに弦はポンピングできます。しましょうu = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p。現在uvxyz = s、任意の iu v^i x y^i zには同量の as と bs があります。
u = a^p、v = b^(p-1)、x = ba、y = a^(p-1)、z = b^p とすると、文字列 s = uvxyz となります。
uv^ixy^iz の形式の任意の文字列が言語に含まれるため、CFL ポンピング補題の条件が満たされます。
あなたの例では、ポンピングの長さは「p」ではありません...おそらくそれがあなたが混乱している場所ですか？
編集: sepp2k は、私の選択した vxy が |vxy| という条件に違反していることを正しく指摘しています。< = p、言語のポンピング長。彼の解 v=b, x=e, y=a は正しいです。この言語では、長さが 2 以上の任意の文字列がポンピングされます。"ab" または "ba" はどこかに出現する必要があるため、vy = ab または vy = ba は常に機能します。