Site navigation

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

Select one answer
Answer and explanation

Correct answer A

L1∩L2L_1 \cap L_2 needs the first two blocks equal and the last two blocks equal, which gives 0n1n0n0^n1^n0^n, that is L3L_3, so A is true. L1L_1 and L2L_2 each match only one pair of blocks, which a pushdown automaton can do, so both are context-free; L3L_3 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 L1L_1 but not to L3L_3.

Practice for these exams

  • UGC NET Computer Science and Applications

Related question papers

Related exam syllabi

Related questions in this topic