Register

CFG to GNF

4,287 views
3 3 votes
Convert the given CFG to GNF.

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

1 Answer

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

Voting & Accepting an answer helps improve the community
← Previous · Peter Linz Edition 4...Next → · general
← Previous in category · Peter Linz Edition 4...Next in category → · TOC regular grammer
Position:
Show:

Related questions

7 7 votes
1 1 answer
37.0k
37.0k views
Menon Karthik asked Dec 14, 2018
37,015 views
CONVERT CFG TO GNF
S→ ABA→ BS|bB→ SA|a INTO GNF
1 1 vote
0 0 answers
5.7k
5.7k views
learner_geek asked Aug 5, 2017
5,660 views
CNF and GNF
Is it mandatory in GNF that first element in production must be terminal(I am considering there is no Left recursion)Is it mandatory in CNF that in production only two no...
1 1 vote
0 0 answers
2.0k
2.0k views
learner_geek asked Aug 5, 2017
1,966 views
CNF and GNF
Given answer is (a) but L->AB i think it is wrong because A and B produce something else Previously, so instead of L->AB there would have given like L->MN M->c1 and N->S ...
1 1 vote
0 0 answers
5.7k
5.7k views
Manu Thakur asked Oct 13, 2017
5,664 views
Automata: Conversion from CFG to CNF
Convert the following context free grammar into Chomsky Normal Form:$S \rightarrow ASA | aB$$A \rightarrow B | S$$B \rightarrow b | \epsilon$Does the appearance of start...