Let's assume that $L_1 = a^nb^{2n}$ and $L_2 = a^na^{2n}$, knowing that $L_1$ is not regular, and $L_2$ is. We also know that regular languages are closed under intersection and union, and complement. What can we say about $L_3 = L_1^\complement$ and $L_4 = L_2^ \complement$?

It seems correct to say $L_4$ is regular, because $L_2$ is, but since $L_1$ is not regular, can we say about $L_3$ the same?

Also, let's assume we have two irregular languages $L_5$ and $L_6$, can we say about their intersection and union as being irregular as well?

  • 1
    $\begingroup$ Are you allowed to refer to the closure property that regular languages are closed under complement? $\endgroup$
    – kviiri
    Dec 21, 2022 at 11:58
  • $\begingroup$ Yes, I am allowed $\endgroup$
    – Papa
    Dec 21, 2022 at 12:01
  • $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Dec 21, 2022 at 23:52

1 Answer 1


Since $L_3$ is the complement of $L_1$, $L_1$ is likewise the complement of $L_3$. If $L_3$ was regular, what would that imply regarding the regularity of $L_1$?

For $L_5$ and $L_6$, consider for example the case where the two languages are each others' complements. Can you determine what languages result from the union and intersection of a language and its complement? Are these languages regular?

  • $\begingroup$ For the last question, the resulting is $L \cap L^\complement = \epsilon$ which is regular. But you re missing something, we only know this: if $L$ is regular, and $L_1$ is regular, then their intersection or union is regular, we can have regular intersection irregular give regular or non regular, and we can have the intersection of two non regular languages give a regular or a non regular. My question is simple, and you repeated my questions $\endgroup$
    – Papa
    Dec 21, 2022 at 12:35
  • $\begingroup$ I am trying to get my facts checked with from someone an expert, that s why I came here $\endgroup$
    – Papa
    Dec 21, 2022 at 12:39

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.