Problem Detail: 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.
Asked By : Iancovici
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10675 Ask a Question Download Related Notes/Documents
