# Regular languages properties

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.

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

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

• 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. Commented Jul 15, 2012 at 19:16
• Ok! Thank u Rick! Commented Jul 15, 2012 at 19:27

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

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.$
• The statement is indeed true. It's not clear to me what you mean by 'E'. Is it $\in$? Commented Jul 15, 2012 at 20:02