解释为上下文无关语言抽取引理?
问题
通过证明xnynzn形式的字符串语言不是上下文无关语言来解释上下文无关语言的泵引理。
解决方案
Pumpinglemma(上下文无关语法)
我们可以使用泵引理证明特定语言不是上下文无关文法。
让我们用矛盾证明的概念
这里我们假设语言是CFG
泵引理的条件
首先考虑一个字符串并分成5个部分,这些部分是pqrst它必须满足以下条件-
|qs|>=1
|qrs|=n(“n”是泵送长度)
pqirsit€L对于不同的i值
让L成为CF语言。
现在我们可以取一个字符串,使得S={xnynzn}
我们将S分为五个部分。
情况1-让n=4所以S=x4y4z4
q和s每个只包含一种类型的符号
xxxyyyyzzzz
p=x,q=xx,r=xyyyyz,s=z,t=zz
让i=2
Pq2rs2吨
xxxxxxyyyyyzzzz
x6y4z5≠L
因为,它不是xnynzn的形式