Изменения

<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>\beta</tex> выводится из <tex>\alpha</tex> за один шаг''' (<tex>(\alpha \Rightarrow \beta)</tex>):# <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex>;# <tex>\beta=\beta_1\beta_2\beta_3</tex>;

'''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' (<tex>(\alpha \Rightarrow^* \beta)</tex>):<tex>\exists \gamma_1, \gamma_2,...\ldots,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \ldots \Rightarrow \gamma_n \Rightarrow \beta</tex>([[Транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <tex>\Rightarrow</tex>).

'''Языком грамматики'''(англ. ''Language of grammar'') называется <tex>L(\Gamma) = \{\omega \in \Sigma^{*}|\mid S \Rightarrow^{*}\omega\}</tex>.

'''Сентенциальная форма'''(англ. ''Sentential form'') — последовательность терминалов и нетерминалов, выводимых из начального символа.

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

<tex>\Sigma = \{(, )\}</tex>;

<tex>$S$\toRightarrow(\boldsymbol{S})\toRightarrow(SS\boldsymbol{S}S)\toRightarrow((S)\boldsymbol{S})\toRightarrow((\boldsymbol{S})(S))\toRightarrow(()(\boldsymbol{S}))\toRightarrow(()())</tex>.

<tex>S\toRightarrow(\boldsymbol{S})\toRightarrow(SS\boldsymbol{S}S)\rightarrow((S)\boldsymbol{S})\rightarrow((\boldsymbol{S})(S))\rightarrow</tex><br/><tex>\rightarrow((SS\boldsymbol{S}S)((S)))\rightarrow (((\boldsymbol{S})S)((S))) \rightarrow ((()\boldsymbol{S})((S)))\rightarrow</tex><br/><tex>\rightarrow((()(\boldsymbol{S}))((S)))\rightarrow ((()())((\boldsymbol{S})))\rightarrow ((()())(()))</tex>.

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

O \rightarrow + | \mid - | \mid * | \mid /\\D \rightarrow 1 | \mid 2 | \mid 3 | \mid 4 | \mid 5 | \mid 6 | \mid 7 | \mid 8 | \mid 9;\\N \rightarrow NN | \mid \varepsilon\\N \rightarrow 0 | \mid 1 | \mid 2 | \mid 3 | \mid 4 | \mid 5 | \mid 6 | \mid 7 | \mid 8 | \mid 9.

Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS Rightarrow SO\rightarrow SOSOS boldsymbol{S} \rightarrow 2OSOS Rightarrow \rightarrow 2O2OS boldsymbol{S} OSOS \rightarrow 2O2O2 Rightarrow 2O \rightarrow boldsymbol{S} OS \Rightarrow 2O2O \boldsymbol{S} \Rightarrow 2 \boldsymbol{O} 2O2 \Rightarrow 2+2O2 2\boldsymbol{O}2 \rightarrow Rightarrow 2+2*2</tex>.

[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] этой же строки: <tex>S \rightarrow SOS Rightarrow \rightarrow 2OS boldsymbol{S}OS \Rightarrow 2\boldsymbol{O}S \rightarrow Rightarrow 2+\boldsymbol{S } \rightarrow Rightarrow 2+SOS \rightarrow boldsymbol{S}OS \Rightarrow 2+2OS 2\boldsymbol{O}S \rightarrow Rightarrow 2+2*\boldsymbol{S } \rightarrow Rightarrow 2+2*2</tex>.

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

<tex>\Sigma = \{0, 1, 2\}</tex>;

$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$Rightarrow 0T\boldsymbol{S} 2 \rightarrow 0$T0TS$Rightarrow 0T0T\boldsymbol{S}22 \rightarrow 0$T0T$01222 Rightarrow 0T0\boldsymbol{T0}1222 \rightarrow Rightarrow 0$T00T1$\boldsymbol{T0}0T1222 \Rightarrow 00\boldsymbol{T0}T1222 \Rightarrow 000T\boldsymbol{T1}222 \rightarrow Rightarrow 000\boldsymbol{T1}1222 \Rightarrow 000111222</tex> Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. <tex>n-1</tex> раз выполняем правило вывода <tex>S \rightarrow 00$T0T$1222 0TS2 </tex>. Потом выполняем правило <tex>S \rightarrow 000$TT$1222 012 </tex>, <tex>n-1</tex> раз выполняем <tex>T0 \rightarrow 000$T$11222 \rightarrow 0001112220T </tex>. После этого у нас получается строка <tex>0^nT^{n-1}2^n</tex>.Выполняем <tex>n-1</tex>раз последнее правило и в результате получаем искомую строку. == См. также ==* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]* [[Иерархия Хомского формальных грамматик|Иерархия Хомского формальных грамматик]]* [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]* [[Правоконтекстные грамматики, эквивалентность автоматам|Правоконтекстные грамматики, эквивалентность автоматам]] == Источники информации==* [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]]* [[wikipedia:Formal_language_theory | Wikipedia {{---}} Formal language]]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)