# Proof that a union of two non-regular languages may be regular

Let $$L_1 = \{ a^{n}b^{m} \mid n > m > 0 \}$$. Describe a non-regular language $$L_2$$ such that $$L_3 = L_1 \cup L_2$$ is regular and $$L_3 ≠ A^{*}$$ (where $$A = \{ a, b \}$$)

From the trace, I cannot prove this with the simple language of $$L= \{ a^{n}b^{m} \mid n,m > 0 \}$$ since it must be different from $$A^{*}$$.

I had thought of $$L_2 = \{ a^{n}b^{m} \mid n ≤ m \} \setminus \{ aab \}$$, so in this way we do not consider a string of $$L_1$$ and the union is different from $$A^{*}$$

• Your choice of $L2$ looks good (but what are you trying to achieve with that ${}-\{aab\}$? After all $aab\notin\{\,a^nb^m\mid n\le m\,\}$) - where are you stuck? Jan 5 at 21:13

## 3 Answers

Let $$L_2 = A^* \setminus (L_1\cup \{\varepsilon\})$$. Then $$L_1 \cup L_2 = A^*\setminus \{\varepsilon\}$$ which is regular and not equal to $$A^*$$.

• and is it equivalent to writing that $L3 = a^{n} b^{m} | n,m > 0 }$ since there is no empty string in $L1$ or $L2$? ($n,m> 0$)
– Luca
Jan 5 at 14:35
• No, because there is no obligations for $b$'s to necessarily follow $a$'s. For example, $baba$ is a word of $L_3$ in my case. Jan 5 at 14:36
• Right, I got confused. So it would have been correct to combine $L1 =${$a^{n} b^{m} | n > m > 0$} with $L2 =${$a^{n}b^{m} | n <= m$} and get $L3 =${$a^{n} b^{m} | n,m > 0$} which is regular?
– Luca
Jan 5 at 14:42
• If you meant $0 < n \leqslant m$ in $L_2$, then yes. Jan 5 at 14:49
• Yes I mean that, thank you now it is clear I was confused about the definition of A*
– Luca
Jan 5 at 14:51

Nowhere does the question state that the intersection of $$L1$$ and $$L2$$ must be empty.

Also for L1 to contain the empty string it must be that $$m = n =0$$ in the description, however $$m,n >0$$, therefore $$L1$$ doesn't contain the empty string.

The obvious solution is for $$L3 = \{ a^*b^* \}$$ (using kleene star) And then figuring out which non-regular language is a superset of $$L3\setminus L1$$.

Though technically saying $$L2 = \{ a^*b^* \} \setminus L1$$ is a sufficient solution assuming they can prove that it is non-regular (which you can do using the fact that intersection, complement and union operations are closed under regular languages). But it's simpler to simply take the $$\{ a^{n}b^{m} | n <= m\}$$ because that fills in all missing pairs of n and m that are missing from $$L1$$.

If you don't want $$L_2$$ to be the complement of $$L_1$$ (as then $$L_3$$ would the set of all words), then you can simply choose $$L_2$$ to be $$\overline{L_1}\setminus L$$, where $$L$$ is a nonempty finite language that is contained in $$\overline{L_1}$$.

Correctness follows from standard closure properties of regular languages, and from the fact that every finite language is regular. So you get in total that $$(\overline{L_1}\setminus L) \cup L = \overline{L_1}$$ Hence, since $$L\in \text{REG}$$ and $$\overline{L_1}\notin \text{REG}$$, we get from regular languages being closed under union that $$\overline{L_1}\setminus L\notin \text{REG}$$. Then, the union $$(\overline{L_1}\setminus L) \cup L_1 = A^* \setminus L = \overline{L}$$ is regular.

Note: In any problem where you are asked to come up with a regular or a non-regular language, then adding or subtracting a finite language from the answer won't change it as regular languages are closed under complementation, intersection (and hence difference -- think why) and union. This is useful in particular for this annoying edge cases where you get a correct answer up to a finite number of words.