# Extended grammar form (backus-naur) and simple grammar forms equivalence

Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -> X[Y]Z has the same effect as the two productions A -> XYZ and A -> XZ.

Curly braces around a grammar symbol or symbols say that these sym­bols may be repeated any number of times, including zero times. Thus, A -> X{YZ} has the same effect as the infinite sequence of productions A -> X, A -> XYZ, A -> XYZYZ, and so on.

Show that these two extensions do not add power to grammars; that is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.

Proof

A -> X[Y]Z     --->        A -> XZ | XYZ

A -> X{YZ}     --->        A -> XB
B -> YZB | ε


How can we prove that both forms will generate the same language?

In the case of optional brackets, this is rather easy. Let us consider your example of a grammar with derivation rule $A \to X[Y]Z$ which is replaced by the derivation rules $A \to XZ$ and $A \to XYZ$. Given a derivation in the original grammar, each application of $A \to X[Y]Z$ replaces $A$ by $XZ$ of by $XYZ$. In the former case, we can simulate this in the new grammar using $A \to XZ$, and in the latter by $A \to XYZ$. Conversely, given a derivation in the new grammar, we can replace each application of the rules $A \to XZ$ and $A \to XYZ$ by an application of $A \to X[Y]Z$.
The case of braces is more complicated. One direction is easy – given a derivation in the original grammar, you can convert it to an equivalent derivation in the new grammar by replacing an application of $A \to X \{YZ\}$ by an equivalent derivation using only the rules $A \to XB$ and $B \to YZB \mid \epsilon$. In the other direction, you have to first show that if $B$ appears in a parse tree, then you can associate with it a path in the tree which corresponds to a derivation of the form $B \to YZB \to (YZ)^2B \to \cdots \to (YZ)^k$ for some $k \geq 0$. Given that, every application of $A \to XB$ can be associated with a path corresponding to a derivation $A \to^* X(YZ)^k$, which can be implemented in the old grammar by the rule $A \to X \{YZ\}$.