上下文無關文法抽取引理

引理

如果L是一個上下文無關語言，則存在一個抽取長度p，使得任何長度≥ p的字串w ∈ L可以寫成w = uvxyz，其中vy ≠ ε，|vxy| ≤ p，並且對於所有i ≥ 0, uvⁱxyⁱz ∈ L。

抽取引理的應用

抽取引理用於檢查文法是否為上下文無關文法。讓我們舉個例子來說明如何檢查。

問題

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

解答

假設L是上下文無關的。那麼，L必須滿足抽取引理。

首先，選擇抽取引理中的一個數n。然後，取 z 為 0ⁿ1ⁿ2ⁿ。

將z分解為uvwxy，其中

|vwx| ≤ n 且 vx ≠ ε。

因此，vwx不能同時包含 0 和 2，因為最後一個 0 和第一個 2 之間的距離至少為 (n+1) 個位置。有兩種情況：

情況 1 - vwx 沒有 2。則vx只包含 0 和 1。則uwy（它必須屬於L）有n個 2，但少於n個 0 或 1。

情況 2 - vwx 沒有 0。

這裡出現了矛盾。

因此，L不是上下文無關語言。