# $\{xx^r\mid x\in L_1, x^r\in L_2\}$ is context-free if $L_1$ and $L_2$ are regular languages

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, 2013 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? Apr 11, 2013 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.