I am studying Automata and stuck in a question that says: Is the following a regular set {a^p, where p is prime} U {even-length strings}?

As we see here this language consists of two sub-languages. The left side one is infinite, and by using prove by pumping lemma, we will wind up that it is not regular. However, the right side one is also infinite but we can build the fsa for it and the regular expression is ((0+1)(0+1))*. So, it regular language.

What I stuck in is that When we Union regular language with non-regular language what is the the final result will be????

From the OR truth table it says to return TRUE value, either of them TRUE or both.

  • $\begingroup$ "From the OR truth table it says to return TRUE value, either of them TRUE or both." -- which table?! $\endgroup$ – Raphael Apr 7 '16 at 15:31
  • 2
    $\begingroup$ For questions like the one in the title, simple examples are worth doing. In this case, empty and everything are both regular. $\endgroup$ – Louis Apr 7 '16 at 15:36
  • $\begingroup$ @Raphael I mean by the truth table is the one that we studied in Logic Design. $\endgroup$ – mab.330 Apr 7 '16 at 15:48
  • $\begingroup$ As Raphael answered, there's no simple rule. Some special cases are trivial, though: $E=\varnothing$ is regular, so if $L$ is non-reguar, then $E\cup L$ will be non-regular. On the other hand, $F=\Sigma^*$ is regular so $F\cup L$ will be regular (for any $L$). $\endgroup$ – Rick Decker Apr 7 '16 at 18:13

There is no simple rule.

Consider the languages

  • $L_1 = \{ a^n b^n \mid n \geq 0\}$,
  • $L_2 = \{ b^n \mid n \geq 0 \}$, and
  • $L_3 = \{ a^n b^m \mid n,m \geq 0 \}$.

Clearly, $L_2$ and $L_3$ are regular while $L_1$ is not. Furthermore,

  • $L_1 \cup L_2$ is not regular but
  • $L_1 \cup L_3$ is.

Therefore, you will have to look more closely at the language at hand and maybe try to proof both claims. Our reference material can help you get started; feel free to post any specific questions about your attempts as new questions.

| cite | improve this answer | |
  • $\begingroup$ Still something is not clear. I review the reference material but still didn't get a clear idea Why L1∪L2 is not regular while L1∪L3 is regular. $\endgroup$ – mab.330 Apr 7 '16 at 15:55
  • 1
    $\begingroup$ $L_1 \cup L_2$ isn't regular because we can still pump $a^nb^n$ strings; $L_2$ doesn't "add" any strings to the language that would cover the results of pumping. $L_1 \cup L_3$ is regular because $L_1 \cup L_3 = L_3$ ($L_1$ is a subset of $L_3$) and $L_3$ is regular. $\endgroup$ – DylanSp Apr 7 '16 at 16:44
  • $\begingroup$ @mab.330 As DylanSp says, you prove it in the same way you prove that $a^nb^n$ is not regular. I think it's clear that you need to go back and review the material, maybe consult a second source. Did you look at that material I linked? $\endgroup$ – Raphael Apr 7 '16 at 19:47

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.