Изменения

То, что <tex> L </tex> — не КС-язык, доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]].  Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]G: * <tex>S \to A \mid B \mid AB \mid BA \mid \epsilon</tex> * <tex>A \to aAa \mid aAb \mid bAa \mid bAb \mid a </tex>* <tex>B \to aBa \mid aBb \mid bBa \mid bBb \mid b </tex> Докажем этот факт. 1. Докажем, что все строки, порождённые G, есть в <tex>\overline{L}</tex>2.Докажем, что все строки из <tex>\overline{L}</tex>, порождаются G