CMI2015-A-09

Question

Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true:

• A. If $L_2$ is regular, then $L_1$ must also be regular.
• B. If $L_1$ is regular, then $L_2$ must also be regular.
• C. Either both $L_1$ and $L_2$ are regular, or both are not regular.
• D. None of the above.

Comments

i think something is missing here?

Answer 1

Answer should be option D.

---

Contradiction for A. Let $L_2 = \{a,b\}^*$ ... which is regular.

And $L_1 = a^nb^n$ which is CFL but not regular.

And here $L_1$ is subset of $L_2$.

---

Contradiction for B. Let $L_1 = ab$ ,

which is regular. And $L_2 = a^nb^n$ which is CFL but not regular.

And here $L_1$ is subset of $L_2$.

C $\rightarrow$ False, ( reason A and B).

Comments

is not ∑ =(a+b)*

---

See here we don't know, what is $\sum$  . I have to take any regular language for L1 and a subset of L1 for L2. So that we can check our options. Whether it is correct or not .

---

that a$^{n}$b$^{n}$ example is very important for a lot other questions too,should be kept in mind always 👍

Answer 2

Suppose L1={aⁿ bⁿ    n≥0}

                   L2=(a+b)*

Here L1⊆ L2

If L2 is regular, then L1 must also be regular. False here.

L1=∈

 L2={aⁿ bⁿ |n≥0}

If L1 is regular, then L2 must also be regular.False here

Fisrt and second makes third false.

So d is correct ans.

Answer 3