You are here
Homeequivalent grammars
Primary tabs
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 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=\SigmaN$ 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}=\varnothing$, then $L(G_{1})=\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 $\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. 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\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\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).
Mathematics Subject Classification
91F20 no label found68Q42 no label found68Q45 no label found03D05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections