3 edited title

2 edited tags
1

# How to prove the following context-free grammar?

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 ?