CFG to GNF

Question

Convert the given CFG to GNF.

$S \rightarrow MN$
$M\rightarrow aMb|\epsilon $
$N\rightarrow aNb|\epsilon $

Comments

i'm not saying its wrong just asking that is there any need of variables A1 and A2

---

@Utkarsh , yes , I think I have taken extra A₁ and  A₂ ...we can replace it by M and N

---

yeah it seems correct otherwise.

Answer 1

Although, @Tuhin Dutta is quite right in his approach. I would just like to add something.

The initial steps involving the conversion (CFG to GNF) actually mention that the UNIT & NULL productions must be removed before the final conversion.

So, I guess that the 'ϵ' would not stay in the final result.

To summarize, here is the solution:

In Step-2, I think the substitution method (to eliminate 'ϵ') will also be applied to 'S' because of which we'll have more number of symbols in the final GNF form.

Different sources tell different methods of doing this conversion so, I'm open to any critical evaluation.