6 6 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 3.6k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 5 5 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 2 2 Comments reply Prajna commented Jun 16, 2019 reply Follow flag is it possible to generate 0001 from option C? 0 0 replyShare Verma Ashish commented Jun 16, 2019 reply Follow flag $S\rightarrow 0S\rightarrow 0SS1\Rightarrow 0001$ 2 2 replyShare Please log in or register to add a comment.
1 1 vote 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 0 reply Please log in or register to add a comment.
