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

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,157 answers

193,767 comments

93,751 users