0
$\begingroup$

I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as regular then $L_1 \cap L_2 = L_3$ makes $L_3$ regular. Now for the case of when $L$ is not regular, then its complement $L^\complement$ is also not regular. But when $L_1$ and $L_2$ are not regular then $L_1 \cap L_2 = L_3$ doesn't make $L_3$ not regular, why? does being closed mean for non regularity too?

$\endgroup$
2
  • 1
    $\begingroup$ Just a simple observation. Take any two language, be it non-regular, with no common strings. Their intersection must be $\emptyset$ which is regular. In general, I think the intersection can be quite arbitrary depending on the languages you are intersecting, so it can either result to a regular language or not. I am not 100% sure here so I am just making this a comment. $\endgroup$
    – Russel
    Nov 11, 2022 at 3:47
  • $\begingroup$ cs.stackexchange.com/q/14462/755 $\endgroup$
    – D.W.
    Nov 11, 2022 at 6:37

2 Answers 2

1
$\begingroup$

Non-regular languages are not closed under intersection.

Let $L_1 = \{aa^nb^n \mid n \ge 0\}$ and $L_2 = \{ba^nb^n \mid n \ge 0\}$. Then $L_1 \cap L_2 = \emptyset$ is regular, but neither $L_1$ nor $L_2$ are regular.

$\endgroup$
0
$\begingroup$

Intersection of 2 non regular languages means the languages could be anything other than regular, and each class of languages have their own set of closure properties. The problem of finding which class a language belongs to is undecidable.

$\endgroup$

Your Answer

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

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