У меня вопрос по конкретной проблеме леммы перекачки для контекстно-свободных языков.
Предположим, у нас есть следующий язык:
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.
У нас есть 6 различных возможностей для 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
Это так до сих пор? Вещи, в которых я не уверен, это правильность моих разных случаев vwx.
заранее спасибо
