Изменения

Перейти к: навигация, поиск

Существенно неоднозначные языки

40 байт добавлено, 01:54, 27 ноября 2011

→‎Существенно неоднозначные языки

===Пример:===

~~Пример такого языка:~~ Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным.

Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>.

Анонимный участник

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/13519»