0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ "From the OR truth table it says to return TRUE value, either of them TRUE or both." -- which table?! $\endgroup$
    – Raphael ♦
    Apr 7, 2016 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, 2016 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, 2016 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, 2016 at 18:13

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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