Изменения
Нет описания правки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: <tex>L = \{a^n b^n c^m d^m | m, n > 1\} \cup \{a^n b^m c^m d^n | m, n > 1\}</tex> - в нем слова вида <tex>a^k b^k c^k d^k</tex> во всех грамматиках имеют более одного дерева разбора.
Докажем это формально:
Единственный способ породить цепочки в которых поровну 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=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
