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

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

Формальная грамматика - четверка [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.