# equivalent grammars

Two formal grammars $G_{1}=(\Sigma_{1},N_{1},P_{1},\sigma_{1})$ and $G_{2}=(\Sigma_{2},N_{2},P_{2},\sigma_{2})$ are said to be equivalent if they generate the same formal languages:

 $L(G_{1})=L(G_{2}).$

When two grammars $G_{1}$ and $G_{2}$ are equivalent, we write $G_{1}\cong G_{2}$.

For example, the language $\{a^{n}b^{2n}\mid n\mbox{ is a non-negative integer}\}$ over $T=\{a,b,c\}$ can be generated by a grammar $G_{1}$ with three non-terminals $x,y,\sigma$, and the following productions:

 $P_{1}=\{\sigma\to\lambda,\sigma\to x\sigma y,x\to a,y\to b^{2}\}.$

Alternatively, it can be generated by a simpler grammar $G_{2}$ with just the starting symbol:

 $P_{2}=\{\sigma\to\lambda,\sigma\to a\sigma b^{2}\}.$

This shows that $G_{1}\cong G_{2}$.

An alternative way of writing a grammar $G$ is $(T,N,P,\sigma)$, where $T=\Sigma-N$ is the set of terminals of $G$. Suppose $G_{1}=(T_{1},N_{1},P_{1},\sigma_{1})$ and $G_{2}=(T_{2},N_{2},P_{2},\sigma_{2})$ are two grammars. Below are some basic properties of equivalence of grammars:

1. 1.

Suppose $G_{1}\cong G_{2}$. If $T_{1}\cap T_{2}=\varnothing$, then $L(G_{1})=\varnothing$.

2. 2.

Let $G=(T,N,P,\sigma)$ be a grammar. Then the grammar $G^{\prime}=(T,N^{\prime},P,\sigma)$ where $N\subseteq N^{\prime}$ is equivalent to $G$.

3. 3.

If $(T_{1},N_{1},P_{1},\sigma_{1})\cong(T_{1},N_{1},P_{2},\sigma_{2})$, then $(T,N,P_{1},\sigma_{1})\cong(T,N,P_{2},\sigma_{2})$, where $T=T_{1}\cup T_{2}$ and $N=N_{1}\cup N_{2}$.

4. 4.

If we fix an alphabet $\Sigma$, then $\cong$ is an equivalence relation on grammars over $\Sigma$.

So far, the properties have all been focused on the underlying alphabets. More interesting properties on equivalent grammars center on productions. Suppose $G=(\Sigma,N,P,\sigma)$ is a grammar.

1. 1.

A production is said to be trivial if it has the form $v\to v$. Then the grammar $G^{\prime}$ obtained by adding trivial productions to $P$ is equivalent to $G$.

2. 2.

If $u\in L(G)$, then adding the production $\sigma\to u$ to $P$ produces a grammar equivalent to $G$.

3. 3.

Call a production a filler if it has the form $\lambda\to v$. Replacing a filler $\lambda\to v$ by productions $a\to va$ and $a\to av$ using all symbols $a\in\Sigma$ gives us a grammar that is equivalent to $G$.

4. 4.

$G$ is equivalent to a grammar $G^{\prime}$ without any fillers. This can be done by replacing each filler using the productions mentioned in the previous section. Finally, if $\lambda\in L(G)$, we add the production $\sigma\to\lambda$ to $P$ if it were not already in $P$.

5. 5.

Let $S(P)$ be the set of all symbols that occur in the productions in $P$ (in either antecedents or conseqents). If $a\in S(P)$, then $G^{\prime}$ obtained by replacing every production $u\to v\in P$ with production $u[a/b]\to v[a/b]$ and $b\to a$, with a symbol $X\notin\Sigma$, is equivalent to $G$. Here, $u[a/b]$ means that we replace each occurrence of $a$ in $u$ with $X$.

6. 6.

$G$ is equivalent to a grammar $G^{\prime}$, all of whose productions have antecedents in $N^{+}$ (non-empty words over $N$).

Remark. In fact, if we let

1. 1.

$X\to XY$,

2. 2.

$XY\to ZT$,

3. 3.

$X\to\lambda$,

4. 4.

$X\to a$

be four types of productions, then it can be shown that

• any formal grammar is equivalent to a grammar all of whose productions are in any of the four forms above

• any context-sensitive grammar is equivalent to a grammar all of whose productions are in any of forms 1, 2, or 4, and

• and any context-free grammar is equivalent to a grammar all of whose productions are in any of forms 1, 3, or 4.

## References

• 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
Title equivalent grammars EquivalentGrammars 2013-03-22 17:37:17 2013-03-22 17:37:17 CWoo (3771) CWoo (3771) 6 CWoo (3771) Definition msc 91F20 msc 68Q42 msc 68Q45 msc 03D05