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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhy 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.
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.
Hint: The intersection of a context-free language with a regular language is still context-free.