0
$\begingroup$

Would it be correct to say that on a operation with a Non-regular language (L) with a Regular language will always return the language L?

I'm came across a property that when we intersect a non-regular language (say L) with Regular Language the resultant result will always remain in Language L.

$L \cap Reg = L$

Does this property extent to other operations too?

$\endgroup$
1
  • 1
    $\begingroup$ $L\cap \varnothing = \varnothing$. $\endgroup$ Jan 29, 2023 at 19:06

1 Answer 1

2
$\begingroup$

For most of the time one can't make sweeping statements about operations between any non-regular language and any regular language. The intuitive reasoning is that regular languages are a very broad collection of languages. Every non-regular language is the subset of a regular language, and every non-regular language has a regular subset (though for some, all regular subsets are finite). Given a regular language $A$ and a non-regular language $B$, you can't eg. know if any of the following are regular or not, without further information on the languages:

  • $A \cap B$ (intersection)
  • $A \cup B$ (union)
  • $A \cdot B$ or $B \cdot A$ (concatenation)
  • $A \setminus B$ or $B \setminus A$ (set difference)
  • Any of the above with either or both languages' complement
  • [countless other operations]

Symmetric difference, as pointed out by HendrikJan in the comments, is one of the few set operations that provably results in a non-regular language when applied between a regular $A$ and a non-regular $B$.

$\endgroup$
4
  • $\begingroup$ That's one reading of the question. On the other hand, if $\mathscr{F}$ is one of the four families in the Chomsky hierarchy and $R$ is a regular language, then $L\in\mathscr{F}\implies L\cap R\in \mathscr{F}$ (Also true for union, I believe.) $\endgroup$
    – rici
    Jan 30, 2023 at 8:10
  • $\begingroup$ @kviiri hey thanks for looking in to the question; my question was whether A op B = B [if A is reg & B is non-reg] or not, but from your answer I'm concluding that it is not really possible to find out whether that's the case $\endgroup$
    – h4kr
    Jan 30, 2023 at 8:55
  • $\begingroup$ @kviiri Symmetric difference seems an exception in your extensive list. First observe regular languages are closed under $\triangle$. Assume that $A$ is regular and $B$ nonregular. Then $A\triangle B$ must be nonregular. Otherwise $B = A\triangle (A\triangle B)$ would be regular. $\endgroup$ Jan 30, 2023 at 12:31
  • $\begingroup$ @HendrikJan Good addition. It was indeed my morning grogginess at play! $\endgroup$
    – kviiri
    Jan 30, 2023 at 13:38

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.