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

Question

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?

Answer 1

Show that given a derivation in one grammar, there is a corresponding derivation in the other grammar which derives the same word. You might find it easier to work with parse trees instead of just derivations.

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\}$.

In the last paragraph I have been vague about some association of vertices in the parse tree to a path and to a derivation, which really amounts do a decomposition of all legal parse trees. These concepts will have to be formalized in a formal proof of equivalence.