Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language?
Trying to understand the approach to determining whether a regular language is context-free.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
1
Regular language is always context-free (but not vice-versa). The language you ask for, $A(L)$, is based on a regular language $L$, but need not be regular.
To show that $A(L)$ (or any other language) is context free, you need to come up with either a context-free grammar that generates $A(L)$, or a PDA that accepts $A(L)$ (or use closure properties of CF languages, as Yuval suggests).
As for the language $A(L)$ in the question, here's a hint for a PDA:
The PDA non-deterministically decides what is the middle-point of the input. during the first half it pushes the input to the stack, and then pops it (in reverse order) and compares it to the rest of the input. In parallel (i.e, using "cross-product" construction), it runs the DFA of $L$ on the input.
-
$\begingroup$ Finding a CFG/PDA does not guarantee that the language is not regular though. You have to show that the language is not regular as well. $\endgroup$ – mrk Mar 21 '13 at 15:16
$\begingroup$
$\endgroup$
Hint: The intersection of a context-free language with a regular language is still context-free.
answered Mar 21 '13 at 3:56
