Formal grammar

Definition

A formal grammar is a tuple $G = (N, \Sigma, P, S)$ where:

1. $N$ is a finite set of nonterminal symbols.
2. $\Sigma$ is a finite alphabet of terminal symbols, disjoint from $N$.
3. $P$ is a finite set of production rules $\alpha \to \beta$, where $\alpha, \beta$ are strings in $(N \cup \Sigma)^*$ and $\alpha$ contains at least one nonterminal.
4. $S \in N$ is the start symbol.

Here $(N \cup \Sigma)^*$ is the Kleene star of $N \cup \Sigma$. For strings $x, y$ over $N \cup \Sigma$, one writes $x \Rightarrow y$ if $x = u \alpha v$ and $y = u \beta v$ for some rule $\alpha \to \beta$ in $P$ and some strings $u, v$. Let $\Rightarrow^*$ be the reflexive and transitive closure of $\Rightarrow$; a chain $x \Rightarrow \cdots \Rightarrow y$ is a derivation. The language generated by $G$ is the formal language $$L(G) = \set{w \in \Sigma^* : S \Rightarrow^* w}.$$