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