Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B →…
2008
Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 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.
{0n 102n | n ≥ 1}
- B.
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l}
- C.
{0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l}
- D.
The set of all strings over {0, 1} containing at least two 0\'s
Attempted by 10 students.
Show answer & explanation
Correct answer: B
Analyze non-terminal A: The rules A → 0A | A0 | 1 generate strings with exactly one '1' surrounded by any number of '0's. Thus, L(A) = {0^i 1 0^j | i, j ≥ 0}.
For S → AA: Concatenating two strings from L(A) results in a string with exactly two '1's. The form is 0^i 1 0^j 1 0^k.
For S → B: The rules B → 0B00 | 1 generate a '1' with n zeros on the left and 2n zeros on the right. Thus, L(B) = {0^n 1 0^{2n} | n ≥ 0}.
The language of S is the union L(AA) ∪ L(B), representing strings with exactly two '1's or strings of the form 0^n 1 0^{2n}.
A video solution is available for this question — log in and enroll to watch it.