# How to show that there is an equivalent context-free grammar

How can I show that for every context free grammar G, there is an equivalent context-free grammar that has production rules with these forms only:

$C→x$WV or $C → λ$, where $x$ is a terminal and $W$ and $V$ are variables.

The permitted rules look similar to Greibach Normal Form where all productions have form: $A → aV_1V_2\dots V_k$ only if $k = 2$ though. However, I'm not sure if that's the correct way to show this.

Your idea with Greibach NF seems not that bad, if you take this for granted then start with this normal form (I assume there are no $\varepsilon$-productions, otherwise some cases must be considered) and then replace iteratively each production $$V \mapsto aV_1 V_2 \cdots V_k$$ with $$V \mapsto aV_1 [V_2 \cdots V_k], \quad [V_2 \cdots V_k] \mapsto bW_1W_2\cdots W_l V_3 \cdots V_k$$ where $[V_2 \cdots V_k]$ denotes a new non-terminal, and $V_2 \mapsto b W_1 W_2 \cdots W_l$ (where this should be done for each such production starting in $V_2$, and these productions should be removed too). As there are just a finite number of productions this procedure terminates with a grammar of the required form.
• The answer given is a good start, but I am afraid that iteratively removing productions will yield longer and longer productions. The construction given will not end? Instead consider $V\to a[V_1\dots V_k]$ and $[V_1\dots V_k] \to b[W_1\dots W_\ell][V_2\dots V_k]$. Omit $[V_2\dots V_k]$ when empty, i.e., $k=1$. Since we are required to have exactly two nonterminals at each right hand side we might add dummy variables $D$ with $D\to\lambda$ as allowed by the grammar format in the question. – Hendrik Jan Jul 1 '15 at 22:19