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