GATE IT 2008 | Question: 34

Question

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:

• A. $\left\{0^n 10^{2n} \mid n \geq 1\right\}$
• B. $\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\}$
• C. $\left\{0^i 10^j \mid i, j \geq 0\right\} \cup \left\{0^n 10^{2n}\mid  n \geq 0\right\}$
• D. The set of all strings over $\{0, 1\}$ containing at least two $0$'s

Comments

@Kushagra गुप्ता

What are those Changes?

---

{0^n10^2n∣n≥0} Assuming originally it was n>=1, which makes None of the options correct, but since the options have been corrected, B is the correct answer.

---

Try producing the string {11}. It will eliminate the options a,c,d.

Answer 1

Lets write the strings generated by the grammar.

S={1,11,0110.......}

Options A,D doesn't have 1

Option C doesn't generate 0110

Therefore Option B

Comments

You can visit https://www.geeksforgeeks.org/gate-gate-it-2008-question-32/ for more formal approach. 

Answer 2

S → AA | B
A → 0A | A0 | 1
B → 0B00 | 1
In this B → 0B00 | 1 which generates {0n 102n | n ≥0}
S → AA | B
A → 0A | A0 | 1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Non-terminal B i s generating the second part of B choice and AA is generating the first part.
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ 0}

None of the above

Answer 3

fact of question is that instead of eliminating the options just find a counter example for each and every option.....nd then try with modified option as mentioned in previous comments........then option b is correct