0 votes 0 votes Theory of Computation theory-of-computation context-free-language conjunctive-normal-form + – KISHALAY DAS asked Dec 10, 2016 retagged Jul 4, 2017 by Arjun KISHALAY DAS 1.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply srestha commented Dec 11, 2016 reply Follow Share @Kishlay plz chk it 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 1 non terminal is enough. $S\rightarrow AB$ $A\rightarrow MA$ $M\rightarrow AC$ $A\rightarrow a$ $B\rightarrow BB$ $B\rightarrow b$ $C\rightarrow D$ $D\rightarrow d$ srestha answered Dec 10, 2016 srestha comment Share Follow See 1 comment See all 1 1 comment reply Mk Utkarsh commented Mar 22, 2018 reply Follow Share unit production 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes Only ONE non-terminal (say E) is required to convert given grammar to CNF. CNF FORM <Variable> → <terminal> or, <Variable> → <variable><variable> S->AB A->AE E->AC B->BB B->b A->a C->d manikantsharma answered Aug 8, 2021 edited Aug 23, 2021 by manikantsharma manikantsharma comment Share Follow See all 2 Comments See all 2 2 Comments reply Aritra779 commented Aug 15, 2021 reply Follow Share I agree. Only with one terminal it can be done. Just the unit production should be removed first. Keeping that there doesn’t make it a CNF. Though removing the unit production wouldn’t change the number of newly added non-terminals. 0 votes 0 votes manikantsharma commented Aug 23, 2021 reply Follow Share corrected. 0 votes 0 votes Please log in or register to add a comment.