1
$\begingroup$

I was reading this question; regarding whether $L=A\cup B$ is nonregular if $A$ is. As is rightly pointed out in that answer, there is no simple rule. But what if we imposed the following conditions:

  1. $A \cap B=\emptyset$
  2. $A\neq B^C$ and $B \neq A^C$

The examples I know of where $L$ fails to be nonregular is where $B$ somehow "makes up" for the nonregularity of $A$, such as setting $B$ as the language of all strings, or the complement of $A$.

But with these new conditions, is there any way for $B$ to turn the union $A\cup B$ into a regular language?

EDIT: Actually, if $L=\{0^n1^m|n,m\geq 0\}$, then

$$L=\{0^n1^n|n\geq 0\} \cup \{0^n1^m|n\neq m\}$$

and both the conditions above are fulfilled. So $L$ can still be regular. Sorry :)

$\endgroup$
1
  • $\begingroup$ If $A \mathrel{\Delta} B^C$ is regular, the argument carries over. $\endgroup$
    – Raphael
    Commented Oct 7, 2019 at 17:12

1 Answer 1

1
$\begingroup$

Here is one result in the direction you're looking into:

Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular.

For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader.

The question you link to concerns the language $$ \{ a^p : p \text{ is prime} \} \cup \{ w : |w| \text{ is even} \} = \{ a^p : p \text{ is an odd prime} \} \cup \{ w : |w| \text{ is even} \}. $$ We can write this in the form $A \cup B$, where $A = \{ a^p : p \text{ is an odd prime}\}$ and $B = \{ w : |w| \text{ is even}\}$. Let $C = \{ w : |w| \text{ is odd} \}$. Applying the result above, we deduce that $A \cup B$ is non-regular (assuming we already know that $A$ is non-regular).

$\endgroup$

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.