3 votes 3 votes A context free grammar for $L=\{w \mid n_0 (w) > n_1 (w)\}$ is given by: $S \rightarrow 0 \mid 0S \mid 1 S S$ $S \rightarrow 0 S \mid 1 S \mid 0 S S \mid 1 S S \mid 0 \mid 1$ $S \rightarrow 0 \mid 0 S \mid 1 S S \mid S 1 S \mid S S 1$ $S \rightarrow 0 S \mid 1 S \mid 0 \mid 1$ Theory of Computation ugcnetcse-june2015-paper3 theory-of-computation context-free-grammar + – go_editor asked Aug 1, 2016 retagged Oct 21, 2018 by Pooja Khatri go_editor 2.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes A. S→0∣0S∣1SS (false since 10001 can't generate) B. S→0S∣1S∣0SS∣1SS∣0∣1 (false since generates 1) C. S→0∣0S∣1SS∣S1S∣SS1 (true) D. S→0S∣1S∣0∣1 (false since 1^+ generated) papesh answered Aug 2, 2016 selected Jan 5, 2017 by papesh papesh comment Share Follow See all 2 Comments See all 2 2 Comments reply Prajna commented Jun 16, 2019 reply Follow Share is it possible to generate 0001 from option C? 0 votes 0 votes Verma Ashish commented Jun 16, 2019 reply Follow Share $S\rightarrow 0S\rightarrow 0SS1\Rightarrow 0001$ 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes C is answer Since b and c produce 1 and a not give all possibility of 0 ans 1. Prashant. answered Aug 2, 2016 Prashant. comment Share Follow See all 0 reply Please log in or register to add a comment.