Порождающая грамматика

Порождающей грамматикой называется $G=(\Gamma ,\Sigma ,P,S)$, где

• $\Gamma$ — алфавит нетерминалов
• $\Sigma$ — алфавит терминалов
• $P$ — множество правил вывода, то есть $\alpha \to \beta$, где $\alpha ,\beta \in (\Sigma \cup \Gamma {)}^{\ast }$ и в $\alpha$ есть хотя бы один нетерминал
• $S\in \Gamma$ — аксиома грамматики

$\Gamma ,\Sigma ,P$ конечны