WW属于{a，b}*上下文无关语言吗？

Question

WW属于{a，b}*上下文无关语言吗？如有，请提供掌上电脑。

Answer 1

不，不是

假设，为了矛盾，它是，那么有一个PDA接受它。

根据抽水引理(对于CFGs)，有一个长度p，使得对于每个单词(我们很快就会选出一个) s有一些子字符串u,v,w,x,y，例如s=uvwxy和：

1. |vwx|<=p
2. |vx|>=1
3. uv^n wx^n y是用于任何正面n的语言。

让我们考虑一下a^p b^p a^p b^p这个词，以及这样的u,v,w,x,y

要么vwx包含单词的中间，要么它完全包含在前半部分，或者它完全包含在下半部分。

如果是在前半部分，那么在单词uv^2 wx^2 y中。我们添加的总长度不超过p，因此我们“移动”了中点不超过p/2，所以现在中间点继续b，但是单词以a开头，所以它不是ww形式的。

同样的论点也适用于下半场。

现在让我们假设它包含中间部分，并考虑uwy (使用n=0)。从|vwx|<=p开始，我们从中间的a和b中移除，但不从边缘的a和b中移除。我们也删除了一个正数的字母，所以uwy的形式是a^p b^k a^m b^p或者是k<p或者m<p。换句话说，它不是ww的形式