Изменения

<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset ((\Sigma \cup N)^* N (\Sigma \cup N)^{+}*) \times (\Sigma\cup N)^{*}\rangle</tex>, где :* <tex>\Sigma</tex> — [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''terminals''), ;* <tex>N</tex> — множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'', в примерах мы будем обозначать их заглавными буквами латинского алфавита), ;* <tex>S</tex> — начальный символ грамматики (англ. ''start symbol''), ;* <tex>P</tex> — набор правил вывода (англ. ''production rules'' или ''productions'') <tex>\alpha\rightarrow \beta</tex>.

* Нетерминалы обозначаются заглавными буквами латинского алфавита(например: <tex>A, B, C</tex>).* Терминалы обозначаются строчными буквами из начала латинского алфавита(например: <tex>a, b, c</tex>).* Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита(например: <tex>\omega</tex>).<br/>* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита(например: <tex>\beta, \alpha</tex>).

<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>

Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.

<tex>S \Rightarrow 0T\boldsymbol{S} 2 \Rightarrow 0T0T\boldsymbol{S}22 \Rightarrow 0T0T0\boldsymbol{0TT0}01222 1222 \Rightarrow 0\boldsymbol{T0}0T1222 \Rightarrow 00\boldsymbol{T0}T1222 \Rightarrow 000T\boldsymbol{T1}222 \Rightarrow 000\boldsymbol{T1}1222 \Rightarrow 000111222</tex> Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. <tex>n-1</tex> раз выполняем правило вывода <tex>S \rightarrow 0TS2 </tex>. Потом выполняем правило <tex>S \rightarrow 012 </tex>, <tex>n-1</tex> раз выполняем <tex>T0 \rightarrow 0T </tex>. После этого у нас получается строка <tex>0^nT^{n-1}2^n</tex>. Выполняем <tex>n-1</tex> раз последнее правило и в результате получаем искомую строку.