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

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

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

Спасибо.


subset context-free-grammar context-free-language
person AIM    schedule 14.11.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Примечание. Далее я упустил ограничение, согласно которому 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 нет.

person rici    schedule 14.11.2016