formal-languages - W 属于 {a,b}* 的 WW 是上下文无关语言吗？

Question

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

Answer 1

不它不是

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

根据抽水引理（对于 CFG），有一个长度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 开头a，所以它不是形式ww

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

现在让我们假设它包含中间，并考虑uwy（使用n=0）。因为|vwx|<=p, 那么我们已经从中间的 a 和 b 中删除了，但没有从边缘的 a 和 b 中删除。我们还删除了正数的字母，uwy形式a^p b^k a^m b^p为 werek<p或m<p。不管怎样，它的形式不是ww