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?
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$– RusselNov 11, 2022 at 3:47
-
$\begingroup$ cs.stackexchange.com/q/14462/755 $\endgroup$– D.W. ♦Nov 11, 2022 at 6:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
