-
Let L1 = { 0n + m 1n 0m | n , m ≥ 0 } , L2 = { 0n + m 1n + m 0m | n , m ≥ 0 } and L2 = { 0n + m 1n + m 0n + m | n , m ≥ 0 } . Which of these languages is/are not context free?
-
- L1 only
- L3 only
- L1 and L2
- L2 and L3
- L1 only
Correct Option: D
The language is context free or not, this can be proved by finding out the grammar for all the languages.
L1 = { 0n + m 1n 0m | n, m ≥ 0 }
The production for L1 as follows :
S → 0S0 | 0A1 | ε
A → 0A1 | ε
Now, we need to apply these values of the production individually to generate
0n + m | n0m
that is,
0m0n 1n0m → To prove
Applying 0S0 (m times)
S → 0 S0, S → 0mS0m
Applying, S → 0A1
→ S → 0m 0A1 0m
Here applying, A → 0 A1, n - 1 times
S → 0m 0 0n - 1 A1n - 1 10m
→ S → 0m 0n 1n 0m
Hence, proved, so L1 is context-free. Going through the same procedure, we can see that two comparisons are made in the L2 language, So it is not context-free.
L3 → Going through the same procedure again, we can see that two comparisons are made in the L3 language, so it is not context free.
