解释上下文无关语言的抽取引理？

问题

通过证明形如 xⁿyⁿzⁿ 的字符串的语言不是上下文无关语言来解释上下文无关语言的抽取引理。

解答

抽取引理 (上下文无关文法)

• 我们可以使用抽取引理证明特定的语言不是上下文无关文法。

• 让我们采用反证法

• 这里我们假设语言是 CFG

抽取引理的条件

首先考虑一个字符串并将其分成五个部分 pqrst，它必须满足以下条件：

• |qs| ≥ 1

• |qrs| = n (“n” 是抽取长度)

• pqⁱrsⁱt ∈ L 对于不同的 i 值

设 L 为 CF 语言。

现在我们可以取一个字符串，使得 S = {xⁿyⁿzⁿ}

我们将 S 分成五个部分。

**情况 1** - 设 n=4，则 S=x⁴y⁴z⁴

q 和 s 各自只包含一种类型的符号

xxxxyyyyzzzz

p=x , q=xx, r=xyyyyz, s=z, t=zz

设 i=2

Pq²rs²t

• xxxxxxyyyyzzzzz

• x⁶y⁴z⁵ ∉ L

因为，它不符合 xⁿyⁿzⁿ 的形式

Bhanu Priya

更新于：2021年6月16日

1K+ 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习