W 属于 {a,b}* 的 WW 是上下文无关语言吗？
Is WW where W belongs to {a,b}* a context free language?
W属于{a,b}*的WW是上下文无关语言吗？
如果是，请提供PDA。
不，不是
假设，为了自相矛盾，它是，然后有一个 PDA 接受它。
根据泵引理（对于 CFG），有一个长度 p 这样对于每个单词（我们将很快选择一个）s 有一些子串 u,v,w,x,y这样 s=uvwxy 和：
|vwx|<=p|vx|>=1uv^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，因此我们的中点 "moved" 不超过 p/2，所以现在中点继续 [=24] =]，但是单词以 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
的形式
W属于{a,b}*的WW是上下文无关语言吗？ 如果是，请提供PDA。
不，不是
假设，为了自相矛盾，它是，然后有一个 PDA 接受它。
根据泵引理（对于 CFG），有一个长度 p 这样对于每个单词（我们将很快选择一个）s 有一些子串 u,v,w,x,y这样 s=uvwxy 和：
|vwx|<=p|vx|>=1uv^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，因此我们的中点 "moved" 不超过 p/2，所以现在中点继续 [=24] =]，但是单词以 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