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

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

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

Пример:

Рассмотрим грамматику [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]0^a 1^b 2^c[/math], где [math]a=b \or b=c[/math] Докажем, что [math]\forall \Gamma \exists k: 0^k 1^k 2^k[/math] имеет хотя бы 2 дерева разбора.

Теорема:

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