Match List I with List II, where L1 is regular, L2 context-free, L3 recursive and L4 recursively enumerable. List I: (a) complement(L3) ∪ L4, (b) complement(L2) ∪ L3, (c) L1* ∩ L2. List II: (i) Context-free language, (ii) Recursively enumerable language, (iii) Recursive language.

1. A(a)-(ii); (b)-(i); (c)-(iii)
2. B(a)-(ii); (b)-(iii); (c)-(i)
3. C(a)-(iii); (b)-(i); (c)-(ii)
4. D(a)-(i); (b)-(ii); (c)-(iii)

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

Show answer & explanation

Correct answer: B. (a)-(ii); (b)-(iii); (c)-(i)

Explanation

Complement of a recursive set is recursive, and union with an RE set is RE. Complement of a CFL is recursive, and union with a recursive set is recursive. A regular set intersected with a CFL is context-free.