0
$\begingroup$

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular:

Prove/Disprove: $C\cup B$ isn't regular.

Thoughts: My intuition says this is true, but I need an idea to prove it. Since I don't know if $C$ as a CFG or RE language I don't know what kind of machine I can build for it.

Improve this question
$\endgroup$
1
  • $\begingroup$ We expect you to make a serious effort before asking here. What methods do you know for proving a language isn't regular? Have you tried each of them? Where did you get stuck, specifically? It looks like you need to make more of an effort on your own -- your textbook will have many worked examples of techniques for proving that specific languages are not regular. So, spend some time trying each one. P.S. I recommend you get clearer on the difference between "$C \cup B$ isn't necessarily regular" vs "$C \cup B$ is never regular". $\endgroup$
    – D.W. ♦
    Commented Jan 26, 2015 at 22:36

1 Answer 1

Reset to default
5
$\begingroup$

Hint 1: Try to prove the contrapositive, namely: if $C\cup B$ is regular and $B$ is finite, then $C$ is regular.

Hint 2: Use closure properties of regular languages.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Strictly speaking, the contrapositive of "If $B$ is finite and $C$ is not regular, then $C\cup B$ is not regular" is "If $C\cup B$ is regular then $B$ is infinite or $C$ is regular". $\endgroup$
    – Rick Decker
    Commented Jan 23, 2015 at 20:04
  • 1
    $\begingroup$ @RickDecker: Unless I first assumed that $B$ is finite and was talking about if $C$ is not regular, then $C\cup B$ is not regular. $\endgroup$
    – Dave Clarke
    Commented Jan 23, 2015 at 20:08
  • 1
    $\begingroup$ I understood that. I was being pedantic, having nothing better to do with my time this afternoon. $\endgroup$
    – Rick Decker
    Commented Jan 23, 2015 at 20:10
  • 2
    $\begingroup$ @RickDecker: I'm watching the TV series Fargo. Very enjoyable. Maybe give that a go. $\endgroup$
    – Dave Clarke
    Commented Jan 23, 2015 at 20:43

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