WW是W所属的{a，b} *上下文无关语言吗？

Question

W是属于{a，b}的上下文无关语言的WW吗？ 如果是，请为其提供PDA。

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