Can every CFG be converted into an equivalent CFG of this form?

Question

Question:

Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables.

For this question, I have considered that it can be proved by using Greibach Normal Form, because we can get the form: A → aABCDEF... which is similar to the form above: A → xBC or A → ϵ.

However,the pre-condition of Greibach Normal Form is that any context-free grammar which doesn’t produce ϵ. I am not sure whether it can prove with GNF.

Can anyone give me suggestions of this proof ?

Answer 1

Since you're allowing $x = \epsilon$ in a production of the form $A \rightarrow xBC$, it seems you can first convert the grammar to Chomsky Normal Form so that every production is of one of the forms $A \rightarrow \epsilon BC$, $A \rightarrow x$, and $A \rightarrow \epsilon$. The only problem is that the productions which produce only a single terminal are not of the form you want, but that isn't too difficult to remedy.