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?
$\begingroup$
$\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$– RaphaelCommented Apr 11, 2013 at 22:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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!
-
$\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$ Commented Apr 11, 2013 at 21:18
-
$\begingroup$ also.. the $x^r$ is just the reverse of $x$ correct? $\endgroup$ Commented 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$– RaphaelCommented Apr 11, 2013 at 22:50
$\begingroup$
$\endgroup$
Hint: you don't need to construct any generator, closure properties are sufficient here.
Details follow later.
