Context-free grammars

A context-free grammar is a quadruple $G=(V,\mathrm{\Sigma },P,S)$ such that:

• $V$ is a finite set of variables.
• $\mathrm{\Sigma }$ is a finite alphabet of terminals, disjoint from $V$.
• $S\in V$ is the start variable.
• $P$ is a finite set of productions of the form $A\to \alpha$, where $A\in V$ and $\alpha$ is a finite word over the alphabet $V\cup \mathrm{\Sigma }$ in the sense of Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$.

The word $\alpha$ may be empty, in which case the production is written $A\to \epsilon$.

• "Context-free" means that the left-hand side of every production is a single variable, independent of the surrounding sentential context.

• The grammar is finite because both the variable set and the production set are finite.