143
правки
Изменения
Превая моя версия
{{Определение
|definition =
'''Нетерминал''' - элемент, представляющий некоторую сущность языка (например часть формулы) и не имеющий конкретного значения.
}}
{{Определение
|definition =
'''Формальная грамматика''' - четверкаэто способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \in N^{*}\times (\Sigma\cup N)^{*}\rangle</tex>
где <tex>\Sigma</tex> - [[алфавит]], <tex>N</tex> - набор нетерминалов, <tex>S</tex> - начальный символ грамматики, <tex>P</tex> - правило вывода <tex>\alpha\rightarrow \beta</tex>
}}
{{Определение
|definition =
'''Терминал''' - элемент фалфавита <tex>\Sigma</tex>
}}
{{Определение
|definition =
<tex>\alpha \Rightarrow \beta</tex> (<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг), если
<tex>\alpha=\alpha_1\alpha_2\alpha_3</tex>
<tex>\beta=\beta_1\beta_2\beta_3</tex>
<tex>\alpha_1=\beta1</tex>
<tex>\alpha_3=\beta3</tex>
<tex>\alpha_2\rightarrow\beta2 \in P</tex>
}}
{{Определение
|definition =
<tex>\alpha \Rightarrow^* \beta</tex> (<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов), если
<tex>\alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta</tex>
}}
{{Определение
|definition =
'''Язык грамматики''' - множество все последовательности терминалов, которые можно получить из начального символа по правилам вывода. <tex>L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}</tex>, где <tex>\Rightarrow^{*} </tex> обозначает, что слово <tex>\omega</tex> выводимо из нетерминала <tex>S</tex> за некоторое число шагов.
}}
