Tomorrow I have my exam and I have still some doubts about some of the following TRUE/FALSE statements about REGULAR LANGUAGES.

Can someone help me and explain me why?

1) For all languages $L_{1}$ and $L_{2}$, if $L_{1} \subseteq L_{2}$, then $L_{1}^{*} \subseteq L_{2}^{*} $, where $L_{1}\neq L_{2}$.

2) For all languages $L_{1}$ and $L_{2}$, if $L_{1} \cap L_{2} = \emptyset $ and $L_{1} \cup L_{2} = \Sigma^{*}$ (the alphabet of $L_1\text{ and }L_2$, then $L_{1} = \overline{L_{2}}$, i.e., the complement of $L_2$.

3) If $L_{1}$ and $L_{2}$ are regular languages, then $(L_{1} \cap L_{2})^{*}\subseteq L_{1}^{*} \cap L_{2}^{*}$.

4) If L is a context-free language, then $L \setminus \{ \epsilon \}$ (where $\epsilon$ is empty string) is a context free grammar.

My answer: TRUE

Reason: if $L$ is a context-free language and $D$ is regular (in our case the Empty String which by definition is a regular language) then their difference is context-free languages.

5) If $L \setminus \{\epsilon\}$ is a regular language, then L is a regular language

My answer: TRUE

Observe that $L \setminus M = L \cap \overline{M}$. We already know that regular languages are closed under complement and intersection.

  • $\begingroup$ There's nothing wrong with changing your answer to (5) to the correct one, but you should mark your change in the edit to include a bit of text like "Edit" to show that you've made an important change to your original post. Otherwise, the answers you get might appear confusing to someone reading them, especially as here where you changed your post after an answer appeared. By the way, best of luck on your exam. $\endgroup$ Commented Jul 15, 2012 at 19:16
  • $\begingroup$ Ok! Thank u Rick! $\endgroup$ Commented Jul 15, 2012 at 19:27

1 Answer 1


1) If $x\in L^*\text{ then }x\in L_1^n$ for some $n\ge 0$ so $x=x_1x_2\cdots x_n$ where $x_i\in L_1$ for $1\le i\le n$. But we know $x_i\in L_1\text{ implies }x_i\in L_2.$ Carry on from there.

2) I'll show half of the result, that $L_1\subseteq \overline{L_2}.$ Let $x\in L_1$. Since $L_1\cap L_2=\emptyset,$ we know $x\notin L_2$, so $x\in \overline{L_2}$. I'll leave containment in the other direction to you.

3) Similar to (1).

4) Your solution is correct.

5) This is actually true. If $\epsilon\notin L$, there's nothing further to prove. If $\epsilon\in L,$ make use of the fact that $(L\setminus \{\epsilon\})\cup \{\epsilon\} = L.$

  • $\begingroup$ About the point 2: if we have that x ∈ L2c and x E L1, we can deduct that L1 is a subset of L2c, so the statement is TRUE. Right? $\endgroup$ Commented Jul 15, 2012 at 19:32
  • $\begingroup$ The statement is indeed true. It's not clear to me what you mean by 'E'. Is it $\in$? $\endgroup$ Commented Jul 15, 2012 at 20:02
  • $\begingroup$ Yes i have meant it... $\endgroup$ Commented Jul 15, 2012 at 20:12
  • $\begingroup$ with 1 and 3 i still struggling.... $\endgroup$ Commented Jul 15, 2012 at 20:48
  • $\begingroup$ What don't you understand? I'll be leaving soon, but perhaps someone else could help if you stated your problem in another post. $\endgroup$ Commented Jul 16, 2012 at 0:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .