Grammar

languages

Definition

Grammar

A grammar is defined as 4-tuple $G=⟨N,T,P,S⟩$, where

• $N$ is the finite set of non-terminal symbols,
• $T$ is the finite set of terminal symbols,
• $P\subseteq (N\cup T{)}^{+}\times (N\cup T{)}^{\ast }$ is the finite set of production rules (relation), and
• $S\in N$ is the start symbol.

Without further constraints, $G$ is called unconstrained grammar or type-0 grammar and is the most general form of a grammar in the Chomsky hierarchy.

Sentential Form

Definition

Sentential Form

Let $G=⟨N,T,P,S⟩$ be a grammar. A word $w\in N\cup T$ is called sentential form if the production rule $S\Rightarrow w$ exists.

The set of all sentential forms over $G$ that can be produced within $n$ steps is given by:

$$SF(G,n)=\{w\in (N\cup T{)}^{\ast }\mid S{\Rightarrow }^{n}w\}$$

Link to original

Generated Language

Definition

Generated Language

The language generated by a grammar $G$ is given by:

$$\mathcal{L}(G)=\{w\in T^{\ast }\mid S{\Rightarrow }^{\ast }w\}$$

Link to original

Equivalence

Two grammars $G_1,G_2$ are called equivalent iff their generated languages match:

$$\mathcal{L}(G_1)=\mathcal{L}(G_2)$$

Examples

$\mathcal{L}(G)=\{a^n{b}^n{c}^n\mid n\ge 1\}$

Let $G=⟨\{S,A,C\},\{a,b,c\},P,S⟩$, where $P$ is the set of production rules:

$$\begin{array}{rl}S& \to abc\mid aAbc\\ A& \to AbC\mid abC\\ Cb& \to bC\\ Cc& \to cc\end{array}$$

The generated language of $G$ is:

$$\mathcal{L}(G)=\{a^n{b}^n{c}^n\mid n\ge 1\}$$