6
$\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?

Improve this question
$\endgroup$
7
  • 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$
    – advocateofnone
    Commented Nov 13, 2015 at 17:37
  • 1
    $\begingroup$ Use the search in this site, this question was asked (and answered) already gazillion times here. $\endgroup$
    – Ran G.
    Commented Nov 13, 2015 at 18:22
  • 1
    $\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
    Commented Nov 13, 2015 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.
    Commented Nov 13, 2015 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
    Commented Nov 13, 2015 at 23:27

2 Answers 2

Reset to default
21
$\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$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ wow, such a nice explaination in few lines :) $\endgroup$
    – Khan Saab
    Commented Oct 29, 2018 at 21:08
5
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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