retagged by
2,809 views
3 votes
3 votes

A context free grammar for $L=\{w \mid n_0 (w) > n_1 (w)\}$ is given by:

  1. $S \rightarrow 0 \mid 0S \mid 1 S S$
  2. $S \rightarrow 0 S \mid 1 S \mid 0 S S \mid 1 S S \mid 0 \mid 1$
  3. $S \rightarrow 0 \mid 0 S \mid 1 S S \mid S 1 S \mid S S 1$
  4. $S \rightarrow 0 S \mid 1 S \mid 0 \mid 1$
retagged by

2 Answers

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)
selected by
1 votes
1 votes
C is answer Since b and c produce 1 and a not give all possibility of 0 ans 1.
Answer:

Related questions

3 votes
3 votes
2 answers
4
go_editor asked Jul 31, 2016
6,456 views
The regular expression corresponding to the language L where $L=\{ x \in \{0,1\}^* \mid x \text{ ends with 1 and does not contain substring 00} $ is(1+01)* (10+01)(1+01)*...