Существенно неоднозначные языки — различия между версиями
KassAK (обсуждение | вклад) |
KassAK (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
Докажем, что <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 дерева разбора. | ||
| − | Лемма | + | {{Лемма |
| + | |statement= | ||
<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> содержат хотя бы по одной выбранной позиции и <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>. | <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> содержат хотя бы по одной выбранной позиции и <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>. | ||
| − | + | |proof= | |
Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1. | Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1. | ||
| Строка 36: | Строка 37: | ||
Лемма доказана. | Лемма доказана. | ||
| − | + | }} | |
Неоднозначность: | Неоднозначность: | ||
Версия 00:21, 16 января 2011
Неоднозначные грамматики
Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора.
Пример:
Рассмотрим грамматику и выводимую цепочку. Ее можно вывести двумя способами:
Эта граматика неоднозначна.
Существенно неоднозначные языки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна. Пример такого языка: , где Докажем, что имеет хотя бы 2 дерева разбора.
| Лемма: |
и в z выбраны хотябы k позиций, то z представимо в виде , где или содержат хотя бы по одной выбранной позиции и содержит не более k выбраных позиций и - нетерминал, такой, что . |
| Доказательство: |
|
Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1. Выбираем Вершина ветвится, если хотя бы 2 ребенка. Если есть сын с помечеными детьми в поддереве - идем в него, ветвится - идем где больше. Вершина ветвится влево, если слева от него есть помеченные листья. Так же определяеся ветвление вправо. Одного из этих типов хотя бы m+2. Пусть m+2 ветвится влево. Рассмотрим нижние m+1 - среди них встретится повторяющийся нетерминал A. Для него уже выполнено условие леммы. В частности uvw - помечены. Из всех прочих выбираем один, в средней части не более k помеченных. Лемма доказана. |
Неоднозначность:
Возьмем k, слово , пометим первые k нулей.
По лемме можно разбить на 5 частей.
По лемме можно породить слово .
Аналогичные рассуждения справедливы для слова , в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. Очевидно, что А и В - разные деревья и одно не является потомком другого. Тогда если дерево разбора в обоих случаях одиниково, то оно порождает слово вида , что не так.
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
| Теорема: |
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика |
