143
правки
Изменения
фикс ссылок
{{Определение
|definition =
'''Терминал''' — элемент [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавита ]] <tex>\Sigma</tex><br/>
Терминалы обозначаются строчными буквами латинского алфавита.
}}
|definition =
'''Формальная грамматика''' — способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где <tex>\Sigma</tex> — [[wiki:Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], <tex>N</tex> — набор нетерминалов, <tex>S</tex> — начальный символ грамматики, <tex>P</tex> — набор правил вывода <tex>\alpha\rightarrow \beta</tex>
}}
Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2</tex>
[[wiki:Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] для такой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2</tex>
