Grammar

languages

Definition

Grammar

A grammar $G$ is a 4-tuple:

$$G=⟨N,T,P,S⟩$$

where:

• $N$ is the finite set of non-terminal symbols
• $T$ is the finite set of terminal symbol ($N\cap T=\{\}$)
• $P\subseteq (N\cup T{)}^{+}\times (N\cup T{)}^{\ast }$ are the product rules
• $S\in N$ is the start symbol

Denote:

• $\alpha \to \beta$ instead of $(\alpha ,\beta )\in P$
• $\alpha \to {\beta }_1|\dots |{\beta }_n$ instead of $\alpha \to {\beta }_1,\dots ,\alpha \to {\beta }_n$

Further, $G$ is also called unconstrained grammar or type- grammar.

Sentential Form

Definition

Sentential Form

Given a grammar $G = \langle N, T, P, S \rangle$$

If $S\Rightarrow w$ holds for a word $w\in (N\cup T{)}^{\ast }$, then $w$ is called a sentential form.

$$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$, denoted $\mathcal{L}(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)$$