0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For (2), considering special cases (in this case, unary languages) can also help. $\endgroup$ – Klaus Draeger Dec 22 '15 at 13:08
  • $\begingroup$ How come (2) can be true if (1) isn't? non-regular languages include CFL languages. $\endgroup$ – johni Dec 22 '15 at 20:41
  • $\begingroup$ No; since all regular languages are also CFLs, there are some CFLs that are regular. (and therefore, there are some CFLs that aren't non-regular) $\endgroup$ – Daniel Martin Dec 22 '15 at 21:22
  • $\begingroup$ I succeeded proving (2), proof by contradiction, thanks for helping. $\endgroup$ – johni Dec 23 '15 at 19:52
  • $\begingroup$ I am curious: how did you connect the regularity of $L'$ with that of $L$ ? $\endgroup$ – Hendrik Jan Dec 24 '15 at 22:50
1
$\begingroup$

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){*} $.

$\endgroup$
-1
$\begingroup$

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".

$\endgroup$
  • 1
    $\begingroup$ For the first part, not every set of palindromes is non-regular. For the third part, closure under union doesn't necessarily help, since $L_1$ might not be regular $\endgroup$ – David Richerby Dec 21 '15 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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