1 votes 1 votes 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? Theory of Computation theory-of-computation context-free-language conjunctive-normal-form simplification + – Manu Thakur asked Oct 13, 2017 Manu Thakur 4.4k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply joshi_nitish commented Oct 14, 2017 i edited by joshi_nitish Oct 14, 2017 reply Follow Share grammer in CNF will be, S-->AS/ SA/ AS'/ A'B/ a A-->AS'/ A'B/ AS/ SA/ a/ b S'-->SA A'-->a B-->b 0 votes 0 votes Manu Thakur commented Oct 14, 2017 reply Follow Share Nitish, Typo! second line productions are for A, not for A'. secondly A->b is missing, added due to null- productions removal. 0 votes 0 votes joshi_nitish commented Oct 14, 2017 reply Follow Share yes, sorry.......accidently!! 0 votes 0 votes Manu Thakur commented Oct 14, 2017 i edited Oct 14, 2017 reply Follow Share @nitish my doubt was if starting variable S appears at RHS in the original Grammar, do we need to add a temp variable? such as S0->S + Original Productions and the we start conversion from cfg to cnf? 0 votes 0 votes joshi_nitish commented Oct 14, 2017 reply Follow Share @manu00x no need for that.. 0 votes 0 votes Manu Thakur commented Oct 14, 2017 reply Follow Share @nitis see the following screenshot taken from the book "Introduction to theory of computation" by Michael Sipser. 0 votes 0 votes Mk Utkarsh commented Mar 24, 2018 reply Follow Share https://gateoverflow.in/188159/chomskey-normal-form?show=188159#q188159 0 votes 0 votes Please log in or register to add a comment.