@Utkarsh , Please check it :-

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

M ----> aB | aA_{1}B

N -----> aB | aA_{2}B

A_{1} ----> aA_{1}B |aB

A_{2} -----> aA_{2}B | aB

A ----> a

B ------> b

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 $

$S \rightarrow MN$

$M\rightarrow aMb|\epsilon $

$N\rightarrow aNb|\epsilon $

+1

@Utkarsh , Please check it :-

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

M ----> aB | aA_{1}B

N -----> aB | aA_{2}B

A_{1} ----> aA_{1}B |aB

A_{2} -----> aA_{2}B | aB

A ----> a

B ------> b

0

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**

+1

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

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

52,215 questions

59,993 answers

201,197 comments

94,663 users