0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would there be a way to solve it without using Greibach Normal Form? $\endgroup$ – stevetronix May 30 '15 at 2:14
  • $\begingroup$ 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? $\endgroup$ – StefanH May 30 '15 at 14:31
  • $\begingroup$ 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. $\endgroup$ – stevetronix May 30 '15 at 18:07
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Jul 1 '15 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.