# Is the union between a regular language and a random language also a regular language?

If not can we draw any conclusion about the newly fromed language, the language that represents the union between a regular language and a non regular language (not context free but a truly random language ).

• Simple thought experiment: what if the two languages have different alphabets? – rici Jan 22 '17 at 3:26
• then the alphabet of the resulting language will be the union of the two alphabets.... however in this exercise we do not care about the alphabet. – yoyo_fun Jan 22 '17 at 3:36
• The point is that the "random language" has not been changed by its union with a disjoint set. It is still precisely the same language, in the same category, and so is the union. On the other hand, if the two languages do intersect, then all bets are off. For example, if both languages have the same alphabet Σ and the regular language is Σ*, then regardless of what the other language is, the union is Σ*, which is regular. – rici Jan 22 '17 at 4:20
• A random language is almost surely (with probability 1) not regular. – Ariel Jan 22 '17 at 4:25
• "Random" or "arbitrary"? The two are not the same! – Raphael Jan 22 '17 at 12:07

The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?
• I couldn't understand this argument. The language described by $a^*b^*$ is regular, yet it contains all strings of the form $a^nb^n$. By your argument, shouldn't it be not regular? What am I missing here? – GoodDeeds Feb 2 '17 at 20:33
• Yes, I agree. What I could not understand was, as per my understanding, in your example, you say $L$ is not regular simply because it contains $a^nb^n$. So, similarly, I could say that $a^*b^*$ contains $a^nb^n$, so it is not regular as well, which would be incorrect. So how is your argument meant to be interpreted as? Thank you. – GoodDeeds Feb 4 '17 at 8:20
• @GoodDeeds The language a*b* is regular even if it contains a^(n)b^(n) since you don't need the use of memory for recognizing every word in the form a*b*. In my example, the words in the form a^(n)b^(n) are not included in a set which can be recognized without the use of memory. – Ack. Feb 5 '17 at 11:45