##### Let L1 and L2 be languages over an alphabet Σ ...

Let L1 and L2 be languages over an alphabet Σ such that L1 ⊆ L2.

Which of the following is true:

(A) If L2 is regular, then L1 must also be regular. | |

(B) If L1 is regular, then L2 must also be regular. | |

(C) Either both L1 and L2 are regular, or both are not regular. | |

(D) None of the above. |

Let A = {w ∈ {a, b}* | w has equal number of as and bs}. It is well known that B is not regular. It is also known that ∅ and {a, b}* are regular.

Now, taking L1 = A and L2 = {a, b}* violates option (a). Taking L1 = ∅ and L2 = A violates option (b). Both the above examples violate option (c). Thus (d) is the correct answer