Register

Automata: Conversion from CFG to CNF

5,651 views
1 1 vote

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 starting symbol S at RHS impacts the conversion from CFG to CNF?

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · DoubtNext → · GATE1996-2.18
← Previous in category · DoubtNext in category → · Context Free Grammar
Position:
Show:

Related questions

0 0 votes
2 2 answers
2.0k
2.0k views
KISHALAY DAS asked Dec 10, 2016
1,973 views
TOC CFG to CNF convertion
1 1 vote
0 0 answers
638
638 views
HenryAsks21 asked May 2, 2022
638 views
Self doubt about CFG to CNF conversion.
I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG: $S \rightarrow bXb \ |\ b...
1 1 vote
0 0 answers
8.0k
8.0k views
Manu Thakur asked Oct 29, 2017
8,013 views
Automata: CFG to CNF
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
1 1 vote
0 0 answers
3.2k
3.2k views
Manu Thakur asked Oct 13, 2017
3,169 views
Automata: Number of Productions in the CFG
Consider the following context free grammar:$S \rightarrow ASA | aB$$A \rightarrow B | S$$B \rightarrow b | \epsilon$How many productions will be there in the modified g...