1 votes 1 votes As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"? Theory of Computation theory-of-computation conjunctive-normal-form + – Manu Thakur asked Oct 29, 2017 Manu Thakur 6.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply joshi_nitish commented Oct 29, 2017 reply Follow Share S->A'A/ AB/ BA/ AA/ A''A/ B'B/ b/ eps A->A''A/ a B->B'B/ b A'->AB A''->a B'->b though answer is D) but CNF can also contain s->eps if start symbol S derive eps, but eps should not present anywhere else than start symbol S.. 1 votes 1 votes Manu Thakur commented Oct 29, 2017 reply Follow Share @nitish yes starting variable can generate epsilon. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes No if there is any Epsilon generations u have to optimize the given CFG and then convert CFG TO CNF. Option A is the correct one. CNF Lakshmi Narayana404 answered Aug 4, 2021 edited Aug 9, 2021 by Lakshmi Narayana404 Lakshmi Narayana404 comment Share Follow See all 2 Comments See all 2 2 Comments reply jugnu1337 commented Aug 9, 2021 reply Follow Share @LakshmiNarayana404 in main production S is generate epsilon but in your answer s dose’nt have any epsilon can you elaborate it? 0 votes 0 votes Lakshmi Narayana404 commented Aug 9, 2021 reply Follow Share For epsilon transitions we need to remove those from CFG while converting to CNF or GNF. Those removal of epsilon transitions is called Elimination of epsilon productions. https://www.sanfoundry.com/automata-theory-cfg-eliminating-null-productions/ and in this problem there also unit productions though https://www.javatpoint.com/automata-simplification-of-cfg this link helps u to remove unit , Epsilon , useless productions from CFG. go to this link ; helps you to remove epsilon productions. @ Thank u and welcome. 0 votes 0 votes Please log in or register to add a comment.