Формальные грамматики

Определение:

Формальная грамматика - четверка [math]\Gamma =\langle \Sigma, N, S \in N, P \in N^{*}\times (\Sigma\cup N)^{*}\rangle[/math] где [math]\Sigma[/math] - алфавит, [math]N[/math] - набор нетерминалов, [math]S[/math] - начальный символ грамматики, [math]P[/math] - правило вывода [math]\alpha\rightarrow \beta[/math]

Определение:

Язык грамматики - множество [math]L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}[/math], где [math]\Rightarrow^{*} [/math] обозначает, что слово [math]\omega[/math] выводимо из нетерминала [math]S[/math] за некоторое число шагов.

То есть, [math]L(\Gamma)[/math] - это все цепочки в алфавите [math]\Sigma[/math], которые выводимы из [math]S[/math] с помощью [math]P[/math].