142
правки
Изменения
Нет описания правки
== Существенно неоднозначные языки ==
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b \vee </tex>, либо <tex>b=c</tex>
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>.
