Изменения

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\RrightarrowRightarrow</tex> для него существует единственное дерево разбора. '''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex> из языка: <tex>\left\vert \upsilon \right\vert < n</tex> все выполненои <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора. Тогда найдем  Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0:</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\taualpha)</tex>. Из того, при этом что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\taualpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности. По предположению для , при этом <tex>\tau:left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \tau beta \right\vert<n\Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора. Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и каждое из них по предположению выводится однозначно). Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[i+10..n-1j]:=(\leftgamma)</tex>, где <tex>j < i</tex>, при этом <tex>\vert gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.  Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[i+10..n-1j] </tex>, где <tex>j > i</tex>, потому что тогда <tex>\right\vertalpha</tex> не будет правильной скобочной последовательностью, так как в позиции <ntex>i</tex> существует единственное дерево разбора баланс скобок будет отрицательный. Значит, из <tex>\Rightarrow(S)</tex> для была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> тоже существует имеет единственное дерево разбора <tex>\Rightarrow</tex> переход доказан, а значит, данная грамматика является однозначная. Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.