Formal grammar (source code)

= Formal grammar
{wiki}

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> is
$$
L(G)=\{w\in\Sigma^*:S\Rightarrow^*w\}.
$$
Intermediate <words> may still contain <nonterminal symbols>; these are <sentential forms>. For example, the <production rules> $S\to aSb$ and $S\to\varepsilon$ give $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ and generate exactly $\{a^nb^n:n\geq0\}$. Restricting each left side to one <nonterminal symbol> gives a <context-free grammar>.<Introduction to the Theory of Computation by Jean Gallier (2017)>[Sections6.1–6.2, printed pp.127–129, context-free grammar and derivation definitions]{ref}