Proving/Disproving that language L is non-regular/CFL

Question

Here are three examples of questions I run into. I'm not looking for solutions.

1. If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular.
2. If $L$ is non-regular then $L' = \{ ww^R | w \in L \}$ is non-regular too.
3. If $L_2, L_3, L_4$ are regular languages and $L_1 \cup L_2 = L_3$ and $L_1 \cap L_2 = L_4$, then $L_1$ is regular.

The problem I'm facing here is that I'm having hard time to figure out what how to prove such claims.

Lets say I'd like to prove claim 1, I can't seem to understand what exactly should I prove? If I assume that $L'$ is regular, then what way can I follow that will lead me to contradiction? I would go for the intersection with CFL language, but this won't help me as CFL is closed under intersection with regular languages. So I'm pretty lost here.

Take claim 3 for example, after spending a lot of time trying to find a counter-example, I have strong feeling that this claim is true. (please don't tell me if I'm wrong, this post is not about the answers). Yet I couldn't find out what exactly should I prove? Of course that $L_1$ is regular but in what way may I do that?

I hope you get my situation. What I'm asking from you is to describe how would your proof be written in the above claims? What would you try to archive in your proof?

Thanks a lot for your time.

Answer 1

In fact it turns out that there is no simple method to prove things like this. Except when you want to disprove a statement, then a well-chosen counter example suffices. But also here there are no guidelines how to find them. Experience and trial and error, I would say. In your three questions I see three different approaches.

For (1) go look for a counter-example. Since the statement is true for most languages, you have to look for trivial special cases, but still contradicting the general claim.

For (2) you can try contra-positive. Instead of $A \Rightarrow B$ consider the equivalent $\lnot B \Rightarrow \lnot A$. This is then a (somewhat exotic) closure property. Can you recover $L$ from $L'$?

And I am afraid that (3) looks like simple Boolean set algebra. It is in fact the most straightforward of the three questions.

Answer 2

For regular languages, my go-to tool is the Myhill-Nerode theorem. Sometimes, for explicitly proving that a language is non-regular, I reach for the pumping lemma.

So my first instincts would be to reach for the pumping lemma for problem 1, and the Myhill-Nerode theorem for problems 2 and 3. The reason that I don't reach for the pumping lemma in problem 2 is because knowing that a language is non-regular gets you very little useful information usually, so I expect that the proof for 2 will have to flow the other way, and that you'll end up proving that if $L'$ is regular, then $L$ is also regular.

Incidentally, I don't believe that proposition 1 is true. After all, what if $L$ is the CFL defined by $S \to aSa \:|\: \epsilon $ ? Then, $L'$ is the regular language given by the regular expression $ (aaaa){*} $.

Answer 3

For 1, it is clear that L' is a palindrome, actually. So, it is really easy to prove that a set of palindromes is non-regular through pumping lemma. Here is one good solution

2nd statement also appears to be pretty much similar.

And for the 3rd statement, you should look into the closure properties of regular languages, especially, "closure under union".