Context-Free Languages の特定のポンピング レンマの問題について質問があります。
次の言語があるとします。
L = {(a^i)(b^j)(c^k)(d^l) | 0 < i < k AND j > l > 0 }
言語が文脈自由ではないことを証明するための私の試みは次のとおりです。
L は文脈自由であると仮定します。補題から定数 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には6つの異なる可能性があります
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
ここまででいいですか？私が確信していないことは、vwx のさまざまなケースが正しいかどうかです。
前もって感謝します