Question

Consider a CFG with the following productions.
$S\to AA|B$
$A\to 0A|A0|1$
$B\to 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. The set of all strings over {0, 1} containing at least two 0's
• B. {$0^i{10}^j|i,j\ge 0$} $\cup$ {$0^n{10}^{2n}|n\ge 1$}
• C. {$0^n{10}^{2n}|n\ge 1$}
• D. {$0^i{10}^j{10}^k|i,j,k\ge 0$} $\cup$ {$0^n{10}^{2n}|n\ge 0$}

Answer 1

The correct option is D {$0^i{10}^j{10}^k|i,j,k\ge 0$} $\cup$ {$0^n{10}^{2n}|n\ge 0$}

$S\to B$
$B\to 0B00|1$
So, S generates {$0^n{10}^{2n}|n\ge 1$}
$S\to AA$
$A\to 0A|A0|1$
$A\to$ {$0^m{10}^n|m,n\ge 0$}
So, S generates {$0^m{10}^n{0}^p{10}^q|m,n,p,q\ge 0$}.
={$0^m{10}^x{10}^q|m,x,q\ge 0$}
={$0^i{10}^j{10}^k|i,j,k\ge 0$}
L(S) = {$0^i{10}^j{10}^k|i,j,k\ge 0$} $\cup$ {$0^n{10}^{2n}|n\ge 1$}
Which is same as option (b).