# $A$ nonregular language, is $A\cup B$ nonregular?

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 :)

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

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).