1
$\begingroup$

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of following type:

$ A \rightarrow a $

$ A \rightarrow aB $

$ A \rightarrow aBC $

My thoughts are that I need to show that every context free rule i can be written into set of context free rules that when applied generate same string as rule i.

Is that correct? If not, could you give me any hints on how to do it properly?

EDIT:

How I`m trying to do it:

Greibach normal form has rules of type:

$A \rightarrow aA_1A_2...A_n$

So I need to break long rules into shorter rules Chomsky normal form style.

$\endgroup$
  • 1
    $\begingroup$ Looks similar to Greibach normal form. Your thoughts are about right; what specifically have you tried and where did you get stuck? $\endgroup$ – Raphael May 11 '16 at 11:11
  • $\begingroup$ @Raphael I'm trying to transform Greibach normal form to this form, and since every CFG could be transformed into GNF that would work, but I'm stalled with that step. $\endgroup$ – TomBombadil May 11 '16 at 12:52
3
$\begingroup$

Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals that represent sequences of old nonterminals, for instance $[A_1A_2\dots A_k]$ is a single symbol that represents the sequence $A_1A_2\dots A_k$ when $k\ge 2$.

Then any production $A\to aA_1A_2\dots A_n$ with $n\ge3$ is replaced by $ A\to a A_1[A_2\dots A_n]$, leaving two nonterminals at the rhs of the production.

Remaining question: what are the productions for terminals $[A_1A_2\dots A_k]$, in such a way that we get only a bounded number of those nonterminals? Well, if $A_1 \to bB_1\dots B_m$ in the original grammar in GNF, then we add the production $[A_1A_2\dots A_k] \to b[B_1\dots B_m][A_2\dots A_k]$ in the new grammar. This can be done for all sequences of nonterminals that are suffixes of the sequences introduced by the original grammar.

Note that we have to take care of short sequences in the obvious way. If in the construction above we find an empty sequence $[\ ]$ it should be omitted, and we write $A$ for the sequence $[A]$ of length one. These special cases occur if $m\le 1$ or $k\le 2$.

$\endgroup$
  • $\begingroup$ FWIW, this is a standard trick that can be seen in the proof of the fact that every CFL has a CFG in Chomsky normal form. $\endgroup$ – Raphael May 19 '16 at 10:13
  • $\begingroup$ I think having rules $A_1 \to b[B_1\dots B_m]$ is nicer than inlining these rules. Nobody can force us to use rule type three. $\endgroup$ – Raphael May 19 '16 at 10:14
  • $\begingroup$ @Raphael Thanks for the suggestions. You are right, I missed the link to CNF, and am overdoing abstractness with introducing $[A]$. I will rewrite. $\endgroup$ – Hendrik Jan May 19 '16 at 11:02

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.