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

Неоднозначные грамматики

Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора.

Пример:

Рассмотрим грамматику [math]E \rightarrow E + E | E * E[/math] и выводимую цепочку[math]E + E * E[/math]. Ее можно вывести двумя способами:

[math]E \Rightarrow E + E \Rightarrow E + E * E[/math]

[math]E \Rightarrow E * E \Rightarrow E + E * E[/math]

Эта граматика неоднозначна.

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

Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. Пример такого языка: [math]L = \{a^n b^n c^m d^m | m, n \gt 1\} \cup \{a^n b^m c^m d^n | m, n \gt 1\}[/math] - в нем слова вида [math]a^k b^k c^k d^k[/math] во всех грамматиках имеют более одного дерева разбора.

Докажем это формально:

Единственный способ породить цепочки в которых поровну a и b — это использовать продукции, похожие на [math]A \rightarrow aAb[/math]. Рассмотрим это более детально:

• Одинковое количество a, b может порождаться продукциями вида [math]A \rightarrow aaabbb[/math],
• продукциями вида [math]A_1 \rightarrow aA_2b|ab[/math], [math]A_2 \rightarrow aA_1b|ab[/math],
• продукциями вида [math]S \rightarrow Ab[/math], [math]A \rightarrow aAb|a[/math]

Но в любом случае парами. Так же с c и d, b и c, a и d. А это значит, что [math]a^k b^k c^k d^k[/math] порождается как минимум двумя способами.

Теорема:

Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика