Изменения

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

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

950 байт убрано, 22:30, 15 января 2011
Нет описания правки
== Существенно неоднозначные языки ==
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: <tex>L = \{0^a1^n b2^n c^m d^m | m</tex>, n где <tex> 1a=b \} \cup \{a^n or b^m =c^m d^n | m, n > 1\}</tex> - в нем слова вида Докажем, что <tex>a^\forall \Gamma \exists k b: 0^k c1^k d2^k</tex> во всех грамматиках имеют более одного имеет хотя бы 2 дерева разбора. Докажем это формально:
Единственный способ породить цепочки в которых поровну a и b {{---}} это использовать продукции, похожие на <tex>A \rightarrow aAb</tex>. Рассмотрим это более детально:
* Одинковое количество a, b может порождаться продукциями вида <tex>A \rightarrow aaabbb</tex>,
* продукциями вида <tex>A_1 \rightarrow aA_2b|ab</tex>, <tex>A_2 \rightarrow aA_1b|ab</tex>,
* продукциями вида <tex>S \rightarrow Ab</tex>, <tex>A \rightarrow aAb|a</tex>
Но в любом случае парами. Так же с c и d, b и c, a и d. А это значит, что <tex>a^k b^k c^k d^k</tex> порождается как минимум двумя способами.
{{Теорема
|statement=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/6947»

Навигация