All mock tests are FREE till 31 December — register to save your progress

If L1 is a regular language and L2 is a context free language, which of the following statement is correct?

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. L1∩L2 is a context free language.

Explanation

It is a standard closure property of context-free languages that the intersection of a context-free language with a regular language is always context-free (proved by a product construction of the CFL's PDA with the regular language's DFA). This intersection need not be regular, and context-free languages in general are not all accepted by a deterministic PDA (only the smaller class of deterministic CFLs is), so option 4 is not guaranteed. Subsets of a context-free union are not guaranteed to be context-free either, since any language whatsoever is a subset of some union. Hence L1∩L2 is context free is the only statement guaranteed to be correct.

More Theory of Computation and Compilers questions