Изменения

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

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

172 байта добавлено, 07:57, 2 декабря 2010
Нет описания правки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: <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> во всех грамматиках имеют более одного дерева разбора.
{{Теорема
|statement=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
Анонимный участник

Навигация