-2
W是屬於{a,b}的上下文無關語言的WW嗎? 如果是,請爲其提供PDA。WW是W所屬的{a,b} *上下文無關語言嗎?
W是屬於{a,b}的上下文無關語言的WW嗎? 如果是,請爲其提供PDA。WW是W所屬的{a,b} *上下文無關語言嗎?
不,它不是
假設,矛盾的緣故,這是,再有就是接受一個PDA。
按照泵引理(對於CFGS),有一個長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