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.

Responses

sumitverma's picture

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

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.