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

  • $\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.