Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Rick Decker Jul 15 '12 at 19:16
    
Ok! Thank u Rick! –  forrestGump Jul 15 '12 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.$

share|improve this answer
    
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? –  forrestGump Jul 15 '12 at 19:32
    
The statement is indeed true. It's not clear to me what you mean by 'E'. Is it $\in$? –  Rick Decker Jul 15 '12 at 20:02
    
Yes i have meant it... –  forrestGump Jul 15 '12 at 20:12
    
with 1 and 3 i still struggling.... –  forrestGump Jul 15 '12 at 20:48
    
What don't you understand? I'll be leaving soon, but perhaps someone else could help if you stated your problem in another post. –  Rick Decker Jul 16 '12 at 0:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.