Here are three examples of questions I run into. I'm not looking for solutions.
- If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular.
- If $L$ is non-regular then $L' = \{ ww^R | w \in L \}$ is non-regular too.
- 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.