解釋上下文無關語言的抽取引理？

問題

透過證明形如 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+ 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習