上下文無關語言的抽象引理

Question

我對上下文無關語言的抽象引理問題有疑問。

假設我們有以下語言：

L = {(a^i)(b^j)(c^k)(d^l) | 0 < i < k AND j > l > 0 } 

這是我學嘗試證明語言不是上下文無關：

假設大號上下文無關。從引理中取常數n> 0。

Let Z = (a^n)(b^n+1)(c^n+1)(d^n), Z ∈ L. 

比根據引理，Z可以寫成Z = uvwxy在以下性能成立：

1. |vx| >= 1 
2. |vwx| <= n 
3. for every i >= 0, u(v^i)w(x^i)y ∈ L. 

我們有VWX

1. vwx = a^i, i <= n 
2. vwx = (a^i)(b^j), i+j <= n 
3. vwx = b^i, i <= n 
4. vwx = (b^î)(c^j), i+j <= n 
5. vwx = (c^i), i <= n 
6. vwx = (c^i)(d^j)), i+j <= n 

這是6種不同的可能性到目前爲止？我不確定的事情是，如果我的vwx的不同情況是正確的。

在此先感謝

Answer 1

到目前爲止，一切都很好，除非你錯過了其中vxy從字符串的結尾完全D的組成情況。