equivalent grammars
Two formal grammars ${G}_{1}=({\mathrm{\Sigma}}_{1},{N}_{1},{P}_{1},{\sigma}_{1})$ and ${G}_{2}=({\mathrm{\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\text{is a nonnegative integer}\}$ over $T=\{a,b,c\}$ can be generated by a grammar ${G}_{1}$ with three nonterminals $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=\mathrm{\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.
Suppose ${G}_{1}\cong {G}_{2}$. If ${T}_{1}\cap {T}_{2}=\mathrm{\varnothing}$, then $L({G}_{1})=\mathrm{\varnothing}$.

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.
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.
If we fix an alphabet $\mathrm{\Sigma}$, then $\cong $ is an equivalence relation on grammars over $\mathrm{\Sigma}$.
So far, the properties have all been focused on the underlying alphabets. More interesting properties on equivalent grammars center on productions. Suppose $G=(\mathrm{\Sigma},N,P,\sigma )$ is a grammar.

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.
If $u\in L(G)$, then adding the production $\sigma \to u$ to $P$ produces a grammar equivalent to $G$.

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 \mathrm{\Sigma}$ gives us a grammar that is equivalent to $G$.

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.
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 \mathrm{\Sigma}$, is equivalent to $G$. Here, $u[a/b]$ means that we replace each occurrence of $a$ in $u$ with $X$.

6.
$G$ is equivalent to a grammar ${G}^{\prime}$, all of whose productions have antecedents in ${N}^{+}$ (nonempty words over $N$).
Remark. In fact, if we let

1.
$X\to XY$,

2.
$XY\to ZT$,

3.
$X\to \lambda $,

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 contextsensitive grammar is equivalent to a grammar all of whose productions are in any of forms 1, 2, or 4, and

•
and any contextfree 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 

Canonical name  EquivalentGrammars 
Date of creation  20130322 17:37:17 
Last modified on  20130322 17:37:17 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 91F20 
Classification  msc 68Q42 
Classification  msc 68Q45 
Classification  msc 03D05 