Union and intersection of a regular and a non-regular language

Problem Detail: 

Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages?

We know that two regular languages always gives us a regular language under all of the above. I can't find anywhere any proof that combination of two languages, one regular and one non-regular results always in a regular or a non-regular language. It seems for me that it should be a non-regular in all above cases. Am I wrong?

Asked By : Dick Tracy

Answered By : David Richerby

Note that the languages $\emptyset$, $\{\epsilon\}$ and $\Sigma^*$ are regular. Let $L_2$ be any non-regular language over $\Sigma$.

Union. $\emptyset \cup L_2 = L_2$, which is non-regular; $\Sigma^*\cup L_2 = \Sigma^*$, which is regular.

Intersection. $\Sigma^*\cap L_2 = L_2$; $\emptyset\cap L = \emptyset$.

Subtraction. $\Sigma^*\setminus L_2 = \overline{L_2}$, which is non-regular, since regular languages are closed under complementation. That is, if $\overline{L_2}$ were regular, then $\overline{\overline{L_2}}=L_2$ would also have to be regular. $\emptyset\setminus L_2 = \emptyset$, which is regular.

Concatenation. $\{\epsilon\}\cdot L_2 = L_2$; $\emptyset\cdot L_2 = \emptyset$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49448