0

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.

stevetronix
  • 433

1 Answers1

0

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.

StefanH
  • 18,086
  • Would there be a way to solve it without using Greibach Normal Form? – stevetronix May 30 '15 at 02:14
  • Of course, often in such problems it helps to do some simple examples and then often a general pattern will emerge. Have you tried to convert some simple grammars? And where did you stuck? – StefanH May 30 '15 at 14:31
  • Yes. I converted some context-free grammars using substitution, removing unit productions, removing repeated productions. I'm just not sure how to show that every grammar can have 2 production rules of those forms only. – stevetronix May 30 '15 at 18:07
  • 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 01 '15 at 22:19