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
  • 2
    $\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, 2013 at 22:48

2 Answers 2

1
$\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$
3
  • $\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$ Apr 11, 2013 at 21:18
  • $\begingroup$ also.. the $x^r$ is just the reverse of $x$ correct? $\endgroup$ Apr 11, 2013 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, 2013 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.