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
    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.2012-07-15
  • 0
    Ok! Thank u Rick!2012-07-15

1 Answers 1