# Can every context free grammar be transformed into equivalent grammar of this form?

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.

• Looks similar to Greibach normal form. Your thoughts are about right; what specifically have you tried and where did you get stuck?
– Raphael
May 11 '16 at 11:11
• @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. May 11 '16 at 12:52

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$.

• 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.
– Raphael
May 19 '16 at 10:13
• 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.
– Raphael
May 19 '16 at 10:14
• @Raphael Thanks for the suggestions. You are right, I missed the link to CNF, and am overdoing abstractness with introducing $[A]$. I will rewrite. May 19 '16 at 11:02