2
$\begingroup$

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.

  • 0
    Ok! Thank u Rick!2012-07-15

1 Answers 1

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

  • 0
    What don't you understand? I'll be leaving soon, but perhaps someone else could help if you stated your problem in another post.2012-07-16