Let L1 = { 0n1n0m | n>=1, m>=1 } L2 = { 0n1m0m | n>=1, m>=1 } L3 = { 0n1n0n | n>=1 } Which of the…
\(L_1 \cap L_2\) needs the first two blocks equal and the last two blocks equal, which gives \(0^n1^n0^n\), that is \(L_3\), so A is true. \(L_1\) and \(L_2\) each match…
Choose your answer
Let
L1 = { 0n1n0m | n>=1, m>=1 }
L2 = { 0n1m0m | n>=1, m>=1 }
L3 = { 0n1n0n | n>=1 }
Which of the following are correct statements?
A. L3=L1 ∩ L2
B. L1 and L2 are context free languages but L3 is not a context free language
C. L1 and L2 are not context free languages but L3 is a context free language
D. L1 is a subset of L3
Answer and explanation
Correct answer A
needs the first two blocks equal and the last two blocks equal, which gives , that is , so A is true. and each match only one pair of blocks, which a pushdown automaton can do, so both are context-free; needs three equal blocks and is not context-free (pumping lemma), so B is true and C is false. D is false because 0011000 belongs to but not to .
Practice for these exams
-
UGC NET Computer Science and Applications