Изменения

'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется [[Формальные грамматики|грамматика]], у которой в левых частях всех правил стоят только одиночные нетерминалы.

:<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы

Выведем слово <tex>"(()(()))()"</tex>:

'''База:''':Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. :Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.

'''ИндукцияИндукционный переход:''':Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2 \dots ldots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.:# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.:# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.

Заметим, что <tex>\omega = \omega_1\omega_2 \dots ldots \omega_k</tex>.

:Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\dots ldots X_k</tex>.:Затем для <tex>i = 1, 2, \dotsldots, k\ </tex> покажем, что имеет место следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots ldots X_k</tex>

Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\dots ldots X_k</tex>.

Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_{i–1}X_iX_{i+1}\dots ldots X_k</tex>

# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots ldots X_k</tex># Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\dots ldots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:

::<tex>\omega_1\omega_2\dotsldots\omega_{i–1}X_iX_{i+1}\dots ldots X_k \Rightarrow_{lm}</tex>

::<tex>\omega_1\omega_2\dotsldots\omega_{i–1}\alpha_1X_{i+1}\dots ldots X_k \Rightarrow_{lm}</tex>

::<tex>\omega_1\omega_2\dotsldots\omega_{i–1}\alpha_2X_{i+1}\dots ldots X_k \Rightarrow_{lm}</tex>

::<tex>\dotsldots</tex>

::<tex>\omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots ldots X_k</tex>

Результатом является порождение <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dotsldots\omega_iX_{i+1}X_{i+2}\dots ldots X_k</tex>.

|proof=Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.

:<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы

'''База:''':Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</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..\ldots i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..\ldots i]=(\alpha)\ </tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..\ldots n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \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[0..\ldots j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

:Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..\ldots j]\ </tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..\ldots i]=(\alpha)\ </tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

:Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..\ldots i] \Rightarrow \omega\ </tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|'''существенно неоднозначными'']]'.{{main|Существенно неоднозначные языки}}