上下文無關語言中的抽吸引理

Question

A = {0^a 1^b 2^c | a < b < c} 

我需要證明A不是上下文無關的。我猜我必須使用Pumping引理來解決這個問題，但是如何？

Answer 1

目標是證明對於長度> =最小抽吸長度的任何弦，弦不能被泵送。也就是說，如果將其拆分爲子條形碼uvxyz，則製作v和y的拷貝（或刪除拷貝）所產生的字符串仍然是語言A。

請注意，您只需要表明，在語言中的一個字符串不能抽（只要滿足最低的泵送長度P）

考慮這個語言，它與A：

Answer 2

第一步：計算出你的最小抽吸長度（2^p + 1），其中p是變量的數量。 第二步：製作一段長度的字符串。 第三步：開始將字符串切割成vwxyz，使得| wy |> 0（注意| x |可以爲零）並且| wxy | < = 2^p + 1。看看你可以定義w和y的各種方式，以及當你開始重複這些子串時會發生什麼。

的關鍵是可能會是0和1