[Solved]: Proving/Disproving that language L is non-regular/CFL

Problem Detail: 

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.

Asked By : johni

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51014

3.2K people like this

 Download Related Notes/Documents