Существенно неоднозначные языки — различия между версиями
| Строка 14: | Строка 14: | ||
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. | Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. | ||
Пример такого языка: <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> во всех грамматиках имеют более одного дерева разбора. | Пример такого языка: <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= | ||
| + | Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}} | ||
Версия 07:57, 2 декабря 2010
Неоднозначные грамматики
Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора.
Пример:
Рассмотрим грамматику и выводимую цепочку. Ее можно вывести двумя способами:
Эта граматика неоднозначна.
Существенно неоднозначные языки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. Пример такого языка: - в нем слова вида во всех грамматиках имеют более одного дерева разбора.
| Теорема: |
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика |
