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