394
правки
Изменения
→Определения
|definition =
'''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где <tex>\Sigma</tex> — [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами'''(англ. ''terminals''), <tex>N</tex> — множество, элементы которого называют '''нетерминалами'''(англ. ''nonterminals''), <tex>S</tex> — начальный символ грамматики, <tex>P</tex> — набор правил вывода(англ. ''production rules'') <tex>\alpha\rightarrow \beta</tex>.
}}
|definition =
'''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' (<tex>\alpha \Rightarrow^* \beta</tex>):
<tex>\exists \gamma_1, \gamma_2,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta</tex>(рефлексивноРефлексивно-транзитивное замыкание отношения <tex>\Rightarrow</tex>).
}}
{{Определение
|definition =
'''Языком грамматики'''(англ. ''Language of grammar'') называется <tex>L(\Gamma) = \{\omega \in \Sigma^{*}|S \Rightarrow^{*}\omega\}</tex>.
}}
|id=sform
|definition =
'''Сентенциальная форма'''(англ. ''Sentential form'') — последовательность терминалов и нетерминалов, выводимых из начального символа.
}}
