Formal grammar

A formal grammar specifies how to generate a formal language by repeated applications of production rules. Write $G=(N,\Sigma ,P,S)$, where $N$ is a finite set of nonterminal symbols, $\Sigma$ is a disjoint finite alphabet of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite set of production rules $\alpha \to \beta$. In an unrestricted formal grammar, the word $\alpha$ must contain at least one nonterminal symbol; $\beta$ may be any word over $N\cup \Sigma$.

A grammar derivation replaces an occurrence of $\alpha$ inside a word by $\beta$. The generated formal language isIntermediate words may still contain nonterminal symbols; these are sentential forms. For example, the production rules $S\to aSb$ and $S\to \epsilon$ give $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ and generate exactly $\{a^n{b}^n:n\ge 0\}$. Restricting each left side to one nonterminal symbol gives a context-free grammar.^[ref]