Изменения

{{Определение|definition ='''Нетерминал''' - элемент, представляющий некоторую сущность языка (например часть формулы) и не имеющий конкретного значения.}}= Определения ==

'''Формальная грамматика''' - это (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку<tex>\Gamma =\langle \Sigma, N, S \in N, P \in subset ((\Sigma \cup N)^* N (\Sigma \cup N)^{*}) \times (\Sigma\cup N)^{*}\rangle</tex>, где :* <tex>\Sigma</tex> - — [[wiki:Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''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>\alpha_1=\beta_1</tex>, <tex>\alpha_3=\beta_3</tex>, <tex>\alpha_2\rightarrow\beta_2 \Sigmain P</tex>.

<tex>\alpha \Rightarrow \beta</tex> ('''<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг), если ноль или более шагов''' <tex>(\alpha=\alpha_1Rightarrow^* \alpha_2\alpha_3beta)</tex>:<tex>\beta=exists \gamma_1, \gamma_2, \ldots,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \beta_1gamma_2 \beta_2Rightarrow \beta_3</tex> <tex>ldots \alpha_1=Rightarrow \beta1</tex> <tex>gamma_n \alpha_3=Rightarrow \beta3beta</tex> ([[Транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <tex>\alpha_2\rightarrow\beta2 \in PRightarrow</tex>).

'''Языком грамматики''' (англ. ''Language of grammar'') называется <tex>\alpha \Rightarrow^* \beta</tex> L(<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шаговGamma), если <tex>= \alpha {\Rightarrow omega \gamma_1 in \Rightarrow Sigma^{*} \gamma_2 mid S \Rightarrow ... ^{*}\Rightarrow omega\gamma_n \Rightarrow \beta}</tex>.

|id=sform|definition = '''Язык грамматикиСентенциальная форма''' (англ. ''Sentential form' - все последовательности ') — последовательность терминалови нетерминалов, которые можно получить выводимых из начального символа по правилам вывода. <tex>L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}</tex>

<tex>\Sigma = \{(, )\}</tex><br/><tex>\begin{array}{lcr}S \rightarrow to (S)\\S \to SS \\S \to \varepsilon\end{array}</tex>

Вывод строки <tex>(()())</tex>:<br/><tex>S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\Rightarrow((S)\boldsymbol{S})\Rightarrow((\boldsymbol{S})(S))\Rightarrow(()(\boldsymbol{S }))\rightarrow SSRightarrow(()())</tex>.

Вывод строки <tex>((()())(()))</tex>:<br/><tex>S \Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\rightarrow ((S)\epsilonboldsymbol{S})\rightarrow((\boldsymbol{S})(S))\rightarrow</tex><tex>\rightarrow((\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, +, *, /, -, (()(), )\}</tex>:<tex>S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())<br/tex>

===Арифметические выражения===<tex>\Sigma = begin{array}{lcr}S \rightarrow S O S\\S \rightarrow (S)\\S \rightarrow 0\\S \rightarrow DN\\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.\end{array}</tex><br/> Вывод строки <tex>2+2*2</tex>: <tex>S \Rightarrow SO\boldsymbol{S} \Rightarrow \boldsymbol{S} OSOS \Rightarrow 2O \boldsymbol{S} OS \Rightarrow 2O2O \boldsymbol{S} \Rightarrow 2 \boldsymbol{O} 2O2 \Rightarrow 2+2\boldsymbol{O}2 \Rightarrow 2+2*2</tex>. [[Контекстно-свободные грамматики, 9вывод, 0лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] этой же строки: <tex>S \Rightarrow \boldsymbol{S}OS \Rightarrow 2\boldsymbol{O}S \Rightarrow 2+\boldsymbol{S} \Rightarrow 2+, \boldsymbol{S}OS \Rightarrow 2+2\boldsymbol{O}S \Rightarrow 2+2*\boldsymbol{S} \Rightarrow 2+2*, 2</tex>. ===Язык <tex>0^n1^n2^n</tex>=== Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.  <tex>\Sigma = \{0, (1, )2\}</tex>

<tex>S \rightarrow 012 \\S O S\rightarrow 0TS2 \\T0 \rightarrow 0T \\ T1 \rightarrow 11 </tex>

Вывод строки <tex>S \rightarrow (S) 000111222</tex>:

<tex>O S \Rightarrow 0T\boldsymbol{S} 2 \Rightarrow 0T0T\boldsymbol{S}22 \Rightarrow 0T0\boldsymbol{T0}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>раз последнее правило и в результате получаем искомую строку.

<tex>S \rightarrow (1 == См. также ==* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка| 2 Возможность порождения формальной грамматикой произвольного перечислимого языка]]* [[Иерархия Хомского формальных грамматик| 3 Иерархия Хомского формальных грамматик]]* [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность| 4 Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]* [[Правоконтекстные грамматики, эквивалентность автоматам| 5 | 6 | 7 | 8 | 9) N</tex>Правоконтекстные грамматики, эквивалентность автоматам]]