1

我一直在观看很多关于如何证明这一点的视频,并且我得到了关于如何证明这一点的混合信息。

在矛盾的情况下,我得到了两种不同的方法,我想知道哪个是正确的。

例子:

L = {a^nb^n+1 c^n+1: n>=0}

一位消息人士说我可以假设该语言是上下文无关的,选择 u,v,x,y 的子字符串,同时保持这三个约束,即:

  1. 对于所有 i>=0,uv^ixy^iz 都在 A 中
  2. |维| > 0
  3. |vxy|<= p

然后显示被抽出的字符串不在语言中,即使在保持 CFL 的约束的情况下也是如此。如果抽出的字符串不在语言中,那我怎么能表现出矛盾。

另一个消息来源说在选择 vxy 时必须遵循某些规则,即 vxy 必须跨越中点......如果你将字符串分成 5 部分并且不满足约束,那么仅此一项就证明了语言是不是节能灯。

基本上,哪种方法是正确的?划分u,v,x,y的规则是什么?

4

0 回答 0