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

341 Views Asked by At

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.

1

There are 1 best solutions below

4
On

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.