137
правок
Изменения
м
Для одного и того же языка могут {{Утверждение|statement = Существуют языки, которые можно задать одновременно существовать как однозначныеоднозначными, так и неоднозначные грамматикинеоднозначными грамматиками.|proof =Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).
Например, у языка правильных скобочных последовательностей существует однозначная грамматика. Данная грамматика будет иметь видРассмотрим грамматику:
<br>
Нет описания правки
}}
<br>
<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;
Правила:<br>
1) <tex>S\rightarrow (S)S</tex><br>2) <tex>S\rightarrow \varepsilon</tex><br>{{Утверждение|statement = ГрамматикаПокажем, что эта грамматика однозначна. Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, заданная таким образомявляющегося правильной скобочной последовательностью, является однозначнойв данной грамматике существует только одно дерево разбора.|proof '''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rrightarrow</tex> для него существует единственное дерево разбора.Как'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex> из языка: <tex>\left\vert \upsilon \right\vert < n</tex> все выполнено. Тогда найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0:</tex> слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\tau)</tex>, при этом <tex>\tau</tex> и <tex>\omega[i+1..n-1]</tex> {{---то очевидно }} правильные скобочные последовательности. По предположению для <tex>\tau:\left\vert \tau \right\vert<n</tex> и <tex>\omega[i+1..n-1]:(\left\vert \omega[i+1..n-1] \right\vert<n</tex> существует единственное дерево разбора <tex>\Rightarrow</tex> для <tex>\omega</tex> тоже существует единственное дерево разбора <tex>\Rightarrow</tex> переход доказан, а значит, данная грамматика является однозначной.
}}
Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].
