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$; $emptysetcap 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. $emptysetsetminus L_2 = emptyset$, which is regular. Concatenation. ${epsilon}cdot L_2 = L_2$; $emptysetcdot L_2 = emptyset$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49448
