Попытка доказать, что дополнение {a^ib^ic^i} является контекстно-свободным

Question

Я пытаюсь доказать, что дополнение L = {a^ib^ic^i: i> = 1} является свободным от контекста. L дополняет: {w - слово над {a, b, c} *: w не в L}.

Как известно, контекстно-свободные языки закрыты под союзом. Итак, я пытаюсь разделить мой язык (дополнение {a^i b^i c^i}) на контекстно-свободные подмножества, в которых их объединение должно быть контекстно-свободным. Может ли кто-нибудь помочь мне найти подмножества? Каждый раз, когда я пытаюсь, я получаю L *!

спасибо.

Answer 1

Примечание: В нижеследующем, я оставил ограничение, которое L не содержит пустую строку, но для этого требуется только небольшая настройка.

---

Рассмотрите aibjck.

Если i=j и j=k, то у вас есть aibici. И наоборот, если i≠j или j≠k, то у вас есть дополнение aibici.

Другими словами,

L = { aibjck | i=j } ∩ { aibjck | j=k }

и

L' = { aibjck | i≠j } ∪ { aibjck | j≠k }

Легко показать, что каждое подмножество в приведенных выше уравнений является контекстно-свободным. Как вы говорите, контекстно-свободные языки закрыты под союзом, но они не закрыты под пересечением; следовательно, L' не имеет контекста, хотя L нет.