edited by
14,806 views
44 votes
44 votes

Consider a CFG with the following productions.

$S \to AA \mid B$
$A \to 0A \mid A0 \mid 1$
$B \to 0B00 \mid 1$

$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is:

  1. $\left\{0^n 10^{2n} \mid n \geq 1\right\}$
  2. $\left\{0^i 10^j 10^k \mid i, j, k \geq 0\right\} \cup \left\{0^n 10^{2n}\mid n \geq 0\right\}$
  3. $\left\{0^i 10^j \mid i, j \geq 0\right\} \cup \left\{0^n 10^{2n}\mid  n \geq 0\right\}$
  4. The set of all strings over $\{0, 1\}$ containing at least two $0$'s
edited by

7 Answers

Best answer
47 votes
47 votes
$B \to 0B00 \mid 1$

generates $\{0^n10^{2n} \mid  n \geq 0\}$

$S \to AA,$
$A \to 0A \mid A0 \mid 1$

generates $0A0A \to 00A0A \to 00101$, which is there in only B and D choices. D is not the answer as "$00$" is not generated by the given grammar. So, only option left is B and if we see carefully, non-terminal $B$ is generating the second part of $B$ choice and $AA$ is generating the first part.

$\left\{0^i 10^j 10^k \mid i, j, k \geq 0\right\} \cup \left\{0^n 10^{2n}\mid n \geq 0\right\}$
edited by
7 votes
7 votes

S-->AA|B

A-->0A|A0|1

B-->0B00|1

B generates 0^n 1 0^2n

A generates 0^* 1 0^*

And we know S can derive either AA or B

IF we take s-->AA then

s derives 0^*.1 .0^* .0^* .1 .0^* which is equal to  0^* 1 0^* 1 0^*   where we can assume each star with a variable >=0...assume i ,j ,k for three kleen stars

S derives 0^i 1 0^j 1 0^k where i,j,k>=0 and it can also generates 0^n 1 0^2n

 

Therefore it is option B

1 votes
1 votes

I solved this question in below way

Find what given grammar generates

S→AA 

A→0A∣A0∣1

1)S→AA  & A→0A &  A→1    generates   0i10j1

2)S→AA & A→0A & A→A0 &  A→1  generates  0i10j10.

3)S→AA & A→A0 & A→0A  & A→1  generates  0i1000j1.

4)S→AA & A→A0 & A→A0  & A→1  generates  0i100j10.

5)S→B & B→0B00∣1 generates   0i102i

option A not correct as we have strings which ends with 1

option B not correct  as in included extra strings which end with multiple 0, whereas our string ends with at most one zero

option C not correct as we have string which has some 0 in between two zeros

option D not correct as we don't get just 00

hence ans is none of above

 

 

1 votes
1 votes
A− > 0A|A0|1 This production rule individually produces a CFL of the form {0i 10j |i, j ≥ 0}

B− > 0B00|1 This production rule individually produces a CFL of the form {0n102n |n ≥ 0}

S− > AA|B This production rule concatenates A’s CFL with itself and unions it with B’s CFL.

Hence, CFL accepted by the given CFG will be {0n102n|n ≥ 0} ∪ {0i 10j 10k |i, j, k ≥ 0}

According to our derivation, as none of the given CFL matches to our derived CFL, correct option
Answer:

Related questions

39 votes
39 votes
4 answers
1
56 votes
56 votes
6 answers
2
Ishrat Jahan asked Oct 28, 2014
12,408 views
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...