不它不是
出于矛盾考虑，假设有一个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，因此我们将“中点”“移动”了不超过p/2，所以现在中点以继续b，但是单词以a开头a，因此它不是形式ww
下半场也有相同的论点。
现在，假设它包含中间部分，并考虑uwy（使用n=0）。从以来|vwx|<=p，我们已经从中间的a和b中删除了，但没有从边缘的a和b中删除了。我们还删除了正数的字母，因此uwy形式a^p b^k a^m b^p为k<por或m<p。无论哪种方式，都不是ww
| 归档时间： |
|
| 查看次数： |
3236 次 |
| 最近记录： |