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

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

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

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

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

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