我一直在观看很多关于如何证明这一点的视频,并且我得到了关于如何证明这一点的混合信息。
在矛盾的情况下,我得到了两种不同的方法,我想知道哪个是正确的。
例子:
L = {a^nb^n+1 c^n+1: n>=0}
一位消息人士说我可以假设该语言是上下文无关的,选择 u,v,x,y 的子字符串,同时保持这三个约束,即:
- 对于所有 i>=0,uv^ixy^iz 都在 A 中
- |维| > 0
- |vxy|<= p
然后显示被抽出的字符串不在语言中,即使在保持 CFL 的约束的情况下也是如此。如果抽出的字符串不在语言中,那我怎么能表现出矛盾。
另一个消息来源说在选择 vxy 时必须遵循某些规则,即 vxy 必须跨越中点......如果你将字符串分成 5 部分并且不满足约束,那么仅此一项就证明了语言是不是节能灯。
基本上,哪种方法是正确的?划分u,v,x,y的规则是什么?