4
правки
Изменения
м
→Исправлена группировка символов, выделенных жирным, в "Язык 0^n1^n2^n".
|definition =
'''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку
<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>000111222</tex> :
<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> раз последнее правило и в результате получаем искомую строку.
