The Gateway to Computer Science Excellence
+2 votes
Convert the given CFG to GNF.

$S \rightarrow MN$
$M\rightarrow aMb|\epsilon $
$N\rightarrow aNb|\epsilon $
in Theory of Computation by Boss | 511 views

@Utkarsh  , Please check it :-

S ---> aB | aMB | aNB | aMBANB | ɛ

M ----> aB | aA1B

N -----> aB | aA2B

A1 ----> aA1B |aB

A2 -----> aA2B | aB

A  ----> a

B ------> b


I don't think $\epsilon$ would be there since it will be eliminated when we convert into CNF.

S-> MN

M->aMb | $\epsilon$

N-> aNb | $\epsilon$

Remove $\epsilon$ by substitution, we get

S-> MN

M->aMb | ab

N-> aNb | ab

S-> aBN | aMBN

M->aMB | aB

N-> aNB | aB

B-> b


 ϵ  is in the language ..So,it can't be eliminated..In CNF ,  ϵ is also allowed when language contains empty string ..


ankitgupta.1729 why $A_{1}$ and $A_{2}$

by the way language for this grammar is

L = $a^{n}b^{n}a^{m}b^{m} ; m,n \geq0$
@Utkarsh ,Can u please tell me any string which is generated by your grammar and not by my grammar ?
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 A1 and  A2 ...we can replace it by M and N

yeah it seems correct otherwise.

1 Answer

+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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,993 answers
94,663 users