Is the union of two non-regular languages regular?

Question

Given two non-regular languages, is their union regular?

Also, why is L = L₁ ∪ L₂ = {aⁱb^j | i,j >= 0} the union of L₁ = {aⁱb^j | i >= j} and L₂ = {aⁱb^j | i < j}?

Then, what is the union of L₁ = {aⁱb^j | i > j} and L₂ = {aⁱb^j | i < j}?

Query

Do not try to ask several questions in one post. You are currently asking three questions. Consider to edit your question to ask only one question. – Tribble

You might want to ask these kind of questions on math.stackexchange.com instead of here. – Tribble

Or you could ask this at cs.stackexchange.com – Dandle

I'm voting to close this question as off-topic because it is not a computer programming question. – Wellrounded

@RaymondChen Do you think the tags [regular-language] and [computation-theory] (among others) should be removed as well? – Stace

@danportin they can be used in programming questions. Say, you are trying to write a parser for a regular language. – Wellrounded

@RaymondChen Fair enough. I see these questions as occupying a grey area between programming and computer science (if you can even separate the two). – Stace

@danportin I agree that the line can be fuzzy, but this question doesn't even come close to approaching it. There is not the slightest hint of a computer program in this question. – Wellrounded

@RaymondChen Maybe I need to get with the times. These kinds of questions were common on SA before cs.stackexchange existed. – Stace

Answer 1

Given two non-regular languages, is their union regular?

Sometimes they are, sometimes they are not. Take any non-regular language L. Consider the complement of this language, L'. We know that L' is non-regular since the regular languages are closed under complementation (if L' were regular, then (L')' = L would also be regular, a contradiction). Because the union of a language and its complement is the universal language of all strings over the alphabet, a context free language, certainly some pairs of non-regular languages have a regular union. To see that not all non-regular languages have a regular union, consider the languages 0^n 1^n and a^n b^n on the shared alphabet {0, 1, a, b}. It is not hard to see that the union of these two disjoint non-regular languages cannot possible be regular.

Also, why is L = L1 ∪ L2 = {aibj | i,j >= 0} the union of L1 = {aibj | i >= j} and L2 = {aibj | i < j}?

For all integers i and j, either i <= j or j <= i (or both). The <= relation defines a total ordering of the integers. If it is not the case that i <= j, we may write i > j instead to mean not(i <= j). Thus, > can be thought of as sort of a shorthand for a negation. Because L1 requires i >= j (this too is just a different way of writing j <= i) and L2 requires i < j (just another way of writing j > i), and because j <= i and j > i are logical negations of each other, the union - which applies the disjunctive operator to these conditions - results in tautology. That is, the resulting condition is always true - either i >= j or i < j, always - and so all that remains is the shared requirement implicit in the beginning of the set-builder notation that all strings begin with some a and end with some b. Even adding i,j >= 0 to the first one is totally unnecessary, assuming a valid domain for i and j, and in fact the second and third languages don't bother mentioning this restriction.

Then, what is the union of L1 = {aibj | i > j} and L2 = {aibj | i < j}?

The only strings that don't satisfy either i > j or i < j are precisely those for which i = j. That is, strings of the form a^n b^n. The union of L1 and L2, then, is the complement of the language a^n b^n. We know neither language is regular, and we know that a^n b^n is context-free. The complement of a^n b^n may be context-free or not; the context-free languages are not closed under complementation. In fact, it's not hard to see that this language must really be context free:

1. take a CFG G1 for language L1
2. take a CFG G2 for language L2
3. make a CFG G for language L by adding a new start symbol and productions which produce each of the start symbols in G1 and G2, respectively

Raffin

Answer 2

Question 1: Is the union of two non-regular language regular?

Sometimes. The regular, context-free, context-sensitive, recursive and recursively enumerable languages are closed under union. However, the deterministic context-free (DCFL) languages accepted by a deterministic pushdown automaton (DPDA) are not. The standard proof goes something like this. Consider the following languages:

L1 = {aibjck : i,j,k ≥ 0}
L2 = {aibicj : i,j ≥ 0}
L3 = {aibjcj : i,j ≥ 0}
L4 = {aibici : i ≥ 0}

The first language is regular, the second and third DCFL, and the fourth not context-free. If DCFL were closed under union, then since it is closed under complementation, the language

L4c = L1c ∪ L2c ∪ L3c

must be DCFL. By the same token, L4 must be DCFL. This is a contradiction, because L4 is not even context-free. Therefore, DCFL is not closed under union. Finally, we can apply De Morgan's laws and the fact that DCFL is closed under complementation to conclude that DCFL is not closed under intersection.

Conversely, there are non-regular languages whose union is regular. The answer to your second question shows that there are DCFL languages whose union is given by a*b*.

Question 2: The union of L1 = {aibj : i ≥ j} and L2 = {aibj : i < j}.

The union of L1 and L2 is L3 = {aibj : i,j ≥ 0}. Since this is an equality involving sets, we must show that L1 ∪ L2 ⊆ L3 and L3 ⊆ L1 ∪ L2.

1. If u ∈ L1 ∪ L2 then u ∈ L1 or u ∈ L2. If u ∈ L1 then u = aibj where i ≥ j. If u ∈ L2 then u = aibj where i < j. By trichotomy, u = aibj where i,j ≥ 0. Thus, u ∈ L3.
2. If u ∈ L3 then u = aibj where i,j ≥ 0. By trichotomy, either i ≥ j or i < j. If the former, then u ∈ L1. If the latter, then u ∈ L2. Thus, u ∈ L1 ∪ L2.

Question 3: The union of L1 = {aibj : i > j} and L2 = {aibj : i < j}

The union of L1 and L2 is the set of strings aibj where i < j or i > j. This is equivalent to saying that i ≠ j by trichotomy. Therefore, L1 ∪ L2 = {aibj : i ≠ j}.

Stace

It's worth adding that Q2 is a union of non-regular languages where the result is regular, and Q3 is a union of non-regular languages where the result is not regular. Each of the non-regular languages in both questions can be straightforwardly shown to be non-regular by showing that a DFA can't recognise it; a DFA would have to "count" all of the a's and remember that count in order to know how many b's are allowed or not allowed. A DFA of course cannot "remember" an arbitrary natural number, because it has finitely many states. – Monsoon

@Monsoon Good point! I like the DCFL case because that class of languages has the special property of not being closed under union. – Stace