Equivalent Grammars §

---

Equivalent grammars define the same language:

• G A $\to$ Ax | y

• G’ A $\to$ yB B $\to$ yB | $\epsilon$

• L(G) = L(G’)

One grammar may be easier to parse than the other.

Note however that they have very different parse trees, and if the parse tree reflects the semantic structure for the language then the semantic information is lost.

Parse tree for yxx:

See Also §

• Formal Languages