patternMinor
Why is the subset of palindromes of a regular language context-free?
Viewed 0 times
whythepalindromesfreeregularlanguagecontextsubset
Problem
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.
Trying to understand the approach to determining whether a regular language is context-free.
Solution
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.
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.
Context
StackExchange Computer Science Q#10675, answer score: 5
Revisions (0)
No revisions yet.