Grammars

Grammars provide a way to define languages by giving a finite set of rules that describe how the valid strings may be constructed. A grammar $G$ consists of: an alphabet $\Sigma$ of terminal symbols or terminals, a finite set of variables $V$, a set of rewrite rules $P$ or productions, and a start symbol $S$ (a variable):

$$G=(V,\Sigma,P,S).$$

Rewrite rules or productions consist of a left-hand side $\alpha$ and a right-hand side $\beta$: $\alpha\rightarrow\beta$. Their meaning is: replace $\alpha$ with $\beta$.

Left-hand sides $\alpha$ are strings over $V\cup \Sigma$, containing at least one variable from $V$: $\alpha\in (V\cup\Sigma)^*V(V\cup\Sigma)^*$. ^5.1 Right-hand sides are strings over $V\cup \Sigma$: $\beta\in (V\cup\Sigma)^*$

The grammar generates strings in $\Sigma^*$ by applying rewrite rules to the start symbol $S$ until no variables are left. Each time a rule is applied, a new sentential form (string of variables from $V$ and terminals from $\Sigma$) is produced. For each rule $\alpha\rightarrow\beta$, any occurence of a left-hand side $\alpha$ as a subscript of the sentential form may be substituted by $\beta$ to form a new sentential form.

The language generated by the grammar, $L(G)$, is the set of all strings that may be generated in that way. Recursive rewrite rules, that is, those which have the same variable in both the left-hand and the right-hand side of a rule lead to infinite languages (if the grammar has no useless symbols).^5.2

As an example, consider the following grammar,

$$G = (V,\Sigma,P,S)$$

$$V = \{ S, A \}$$

$$\Sigma = \{ {\tt a}, {\tt m}, {\tt o}, {\tt t} \}$$

$$P = \left\{ \begin{array}{rrcl} (1) & S & \rightarrow & {\tt... ...a} \\ (3) & A & \rightarrow & {\tt ma}A \end{array} \right\}$$

which generates the language

$$L(G)=\{ {\tt tomato}, {\tt tomamato}, {\tt tomamamato} \ldots \}.$$

The generation of the string tomamamato would proceed as follows:

$$S \Rightarrow_1 {\tt to}A{\tt to} \Rightarrow_3 {\tt toma}A{\... ...htarrow_3 {\tt tomama}A{\tt to} \Rightarrow_2 {\tt tomamamato}$$

where the subscripted arrows refer to the application of particular rules in $G$.