# Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

I have this problem:

Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.

I am unsure how to prove that some language is context-free. Could someone please provide the steps?

• What have you tried? It's impossible for us to properly help you if you don't share what you've got. This is actually a nice exercise problem. Write down what you know about $L_1$ and $L_2$ and work from there. – Raphael Apr 11 '13 at 22:48

One way to prove that a language is context-free is to find a context-free grammar that recognizes it. Just go through the definition (on Wikipedia for example) and try to find a context-free grammar for $L_3$ (it's easy). Good luck!
• also.. the $x^r$ is just the reverse of $x$ correct? – Matt Hintzke Apr 11 '13 at 21:19
• @MattHintzke You'd have to prove that the grammar generates the language; then, if it's a context-free grammar, you are done. Same goes for PDAs. And yes, $w^r$ typically denotes the reverse, but you'd have to check the definitions given in your course/textbook to make sure. – Raphael Apr 11 '13 at 22:50