0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question; you can not "prove a grammar".. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 4 '17 at 7:43
1
$\begingroup$

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.

$\endgroup$

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.