Изменения

Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|``("S``)"|SS</tex>.# Удалим длинные правила и получим грамматику <tex>\begin{array}{l l} S\rightarrow \varepsilon|A``)"|SS\\ A\rightarrow ``("S\end{array}</tex>.# Удалим &epsilon; правила - <tex>\begin{array}{l l} S\rightarrow \varepsilon|S'\\ S'\rightarrow A``)"|S'S'\\ A\rightarrow ``("S'|``("\end{array}</tex>.# Удалим цепные правила - <tex>\begin{array}{l l} S\rightarrow \varepsilon|A``)"|S'S'\\ S'\rightarrow A``)"|S'S'\\ A\rightarrow ``("S'|``("\end{array}</tex>.# Заменим терминалы на нетерминалы - <tex>\begin{array}{l l} S\rightarrow \varepsilon|AB|S'S'\\ S'\rightarrow AB|S'S'\\ A\rightarrow CS'|``("\\ C\rightarrow ``("\\ B\rightarrow ``)"\end{array}</tex>.