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

上下文無關語言 (CFL) 的抽取引理用於證明一個語言不是上下文無關語言。

假設 L 是上下文無關語言。

則存在一個抽取長度 n，使得任何長度大於等於 n 的字串 w εL 可以寫成如下形式：

|w|>=n

我們可以將 w 分成 5 個字串，w=uvxyz，如下所示：

• |vxy| >=n
• |vy| ≠ ε
• 對於所有 k>=0，字串 uv^kxy^kz∈L

下面解釋了使用抽取引理證明語言不是上下文無關語言的步驟：

• 假設 L 是上下文無關語言。
• 抽取長度為 n。
• 所有長度大於 n 的字串都可以被抽取 |w|>=n。
• 現在在 L 中找到一個字串 'w'，使得 |w|>=n。
• 將 w 分成 uvxyz
• 證明對於某些 k，uv^kxy^kz ∉L
• 然後，考慮 w 可以分成 uvxyz 的方式。
• 證明這些方式中沒有一個能夠同時滿足所有 3 個抽取條件。
• w 無法被抽取（矛盾）。

示例

找出 L={xⁿyⁿzⁿ|n>=1} 是否為上下文無關語言。

解答

• 設 L 為上下文無關語言。
• L 必須滿足抽取長度，例如 n。
• 現在我們可以取一個字串，例如 s=xⁿyⁿzⁿ
• 我們將 s 分成 5 個字串 uvxyz。

設 n=4，則 s=x⁴y⁴z⁴

情況 1

v 和 y 各自只包含一種型別的符號。

（我們只考慮 v 和 y，因為 v 和 y 的冪是 uv²xy²z）

X xx x yyyyz z zz

=uv^kxy^kz 當 k=2

=uv²xy²z

=xxxxxxyyyyzzzzz

=x⁶y⁴z⁵

（x 的數量 ≠ y 的數量 ≠ z 的數量）

因此，結果字串不滿足條件。

x⁶y⁴z⁵ ∉ L

如果一種情況失敗，則無需檢查其他條件。

情況 2

v 或 y 包含多種型別的符號。

Xx xx yy y y zzzz

=uv^kxy^kz (k=2)

=uv²xy²z

=xxxxyyxxyyyyyzzzz

=x⁴y²x²y⁵z²

這個字串不符合我們字串 xⁿyⁿzⁿ 的模式。

Bhanu Priya

更新於：2021年6月12日

31K+ 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習