Изменения

<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 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.

$S $ \rightarrow 012 \\$S $ \rightarrow 0$TS$2 0TS2 \\$T$0 T0 \rightarrow 0$T$ 0T \\ $T$1 T1 \rightarrow 11

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