edited by
1,203 views
13 votes
13 votes

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:

  1. If $L_2$ is regular, then $L_1$ must also be regular.
  2. If $L_1$ is regular, then $L_2$ must also be regular.
  3. Either both $L_1$ and $L_2$ are regular, or both are not regular.
  4. None of the above.
edited by

3 Answers

Best answer
17 votes
17 votes

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).

edited by
8 votes
8 votes

Suppose L1={an bn    n≥0}

                   L2=(a+b)*

Here L1⊆ L2

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

L1=∈

 L2={an bn |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.

edited by
Answer:

Related questions

1 votes
1 votes
1 answer
1
13 votes
13 votes
5 answers
4
go_editor asked May 27, 2016
5,506 views
How many times is the comparison $i \geq n$ performed in the following program?int i=85, n=5; main() { while (i >= n) { i=i-1; n=n+1; } }$40$$41$$42$$43$