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 和:

|vwx|<=p

|vx|>=1

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的形式