0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 11 '13 at 22:48
0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ so you think merely constructing a grammar for it is considered showing or proving it is as the question asks? I was expecting to have to deal with some theory $\endgroup$ – Matt Hintzke Apr 11 '13 at 21:18
  • $\begingroup$ also.. the $x^r$ is just the reverse of $x$ correct? $\endgroup$ – Matt Hintzke Apr 11 '13 at 21:19
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 11 '13 at 22:50
0
$\begingroup$

Hint: you don't need to construct any generator, closure properties are sufficient here.

Details follow later.

$\endgroup$

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.