2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ How did you try proving ? For starters you could come up with examples. eg let $L_1=\{a^ib^i | i \ge 0 \}$ and $L_2=\{\epsilon\}$. What can you say about $L_1$,$L_2$ and their intersection ? $\endgroup$ – sashas Nov 13 '15 at 17:37
  • 1
    $\begingroup$ Use the search in this site, this question was asked (and answered) already gazillion times here. $\endgroup$ – Ran G. Nov 13 '15 at 18:22
  • $\begingroup$ @RanG. Flagging to close as a duplicate of a specific question would be much more helpful! Especially if it's really been answered a gazillion times, in which case almost any search term should rapidly give a near-exact dupe. $\endgroup$ – David Richerby Nov 13 '15 at 21:10
  • 2
    $\begingroup$ @DavidRicherby see for instance, q/35644, and also related (for kleene star) q/28536, and almost similar question yet when one of the languages is decidable, q/33822, etc., and those are only questions that YOU have answered. Searching for duplicates takes time, which the OP should have invested before posting. Of course, I'm not telling you what to do with your time – if you feel the need to support and answer these kind of questions this is definitely your right. $\endgroup$ – Ran G. Nov 13 '15 at 22:05
  • $\begingroup$ @RanG. The first of those questions asks about the intersection of a specific regular language with a specific non-regular language. The second is completely unrelated and I honestly don't know why you're even mentioning it. The third covers only intersection and my answer to it isn't particularly general. None of this justifies your shouty boldface accusations or your claim that the question has been asked "a gazillion times." Where's the dupe? $\endgroup$ – David Richerby Nov 13 '15 at 23:27
13
$\begingroup$

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_2 = \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$.

$\endgroup$
  • 1
    $\begingroup$ wow, such a nice explaination in few lines :) $\endgroup$ – Khan Saab Oct 29 '18 at 21:08
2
$\begingroup$

Let $L_1$ be a regular language and let $L_2$ be an irregular language.

We are going to prove that your intuition($L_1 \cup L_2$, $L_1 \cap L_2$, $L_1 \setminus L_2$, $L_1 \cdot L_2$ are always irregular) is false using counterexamples.

1)For $L_1 \cup L_2$ consider the following counterexample:

$L_1= \mathscr{L}(a^*b^*)$ and

$L_2=\{a^nb^n |n \geq 0\}$

$L_1\cup L_2= L_1$

2)For $L_1 \cap L_2$ consider the following counterexample:

$L_1= \mathscr{L}(c^*)$ and

$L_2=\{a^nb^n |n \geq 0\}$

$L_1\cap L_2=\emptyset$

3)For $L_1 \setminus L_2$ consider the following counterexample:

$L_1= \mathscr{L}(c^*)$ and

$L_2=\{a^nb^n |n \geq 0\}$

$L_1\setminus L_2= L_1$

4)For $L_1 \cdot L_2$ consider the following counterexample:

$L_1= \emptyset$ and

$L_2=\{a^nb^n |n \geq 0\}$

$L_1 \cdot L_2= L_1 = \emptyset$

Finally we can't guarantee that the union. intersection, subtraction or concatenation of this languages are irregular always.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your elaborated answer, I understand now everything :] $\endgroup$ – Dick Tracy Nov 13 '15 at 18:33
  • $\begingroup$ @DavidRicherby thanks for your feedback. I will edit my answer to make it more clear. $\endgroup$ – Renato Sanhueza Nov 13 '15 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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