0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Simple thought experiment: what if the two languages have different alphabets? $\endgroup$ – rici Jan 22 '17 at 3:26
  • $\begingroup$ 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. $\endgroup$ – yoyo_fun Jan 22 '17 at 3:36
  • $\begingroup$ 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. $\endgroup$ – rici Jan 22 '17 at 4:20
  • 1
    $\begingroup$ A random language is almost surely (with probability 1) not regular. $\endgroup$ – Ariel Jan 22 '17 at 4:25
  • 2
    $\begingroup$ "Random" or "arbitrary"? The two are not the same! $\endgroup$ – Raphael Jan 22 '17 at 12:07
7
$\begingroup$

The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?

$\endgroup$
4
$\begingroup$

Suppose L1 = a* (regular language) and L2=anbn, where n is a natural number (L2 is not regular).

L = L1 U L2 = {ε, a, aa, aaa, ..., ab, aabb, aaabbb, ... } but there is no DFA able to recognize words in the form anbn, so L is not regular.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – GoodDeeds Feb 2 '17 at 20:33
  • $\begingroup$ @GoodDeeds The automata that recognizes the language in your example doesn't need to count the occurrences of "a" and "b", but checks that there is no "b" on the left side of an "a". You can do this using a DFA, but you can't count the occurrences (if n is a variable, of course). $\endgroup$ – Ack. Feb 4 '17 at 7:57
  • $\begingroup$ 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. $\endgroup$ – GoodDeeds Feb 4 '17 at 8:20
  • $\begingroup$ @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. $\endgroup$ – Ack. Feb 5 '17 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.