390
правок
Изменения
м
→Однозначные грамматики
:Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.
:Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j] \ </tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)\ </tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.
:Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega \ </tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.
