2,687 views
3 votes
3 votes
Convert the given CFG to GNF.

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

1 Answer

2 votes
2 votes

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.

Related questions

5 votes
5 votes
1 answer
1
1 votes
1 votes
0 answers
2
0 votes
0 votes
2 answers
3