Существенно неоднозначные языки — различия между версиями
| Строка 13: | Строка 13: | ||
== Существенно неоднозначные языки == | == Существенно неоднозначные языки == | ||
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. | Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. | ||
| − | Пример такого языка: <tex> | + | Пример такого языка: <tex>0^a 1^b 2^c</tex>, где <tex>a=b \or b=c</tex> |
| − | + | Докажем, что <tex>\forall \Gamma \exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}} | Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}} | ||
Версия 22:30, 15 января 2011
Неоднозначные грамматики
Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора.
Пример:
Рассмотрим грамматику и выводимую цепочку. Ее можно вывести двумя способами:
Эта граматика неоднозначна.
Существенно неоднозначные языки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. Пример такого языка: , где Докажем, что имеет хотя бы 2 дерева разбора.
| Теорема: |
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика |
