patternMinor
First half of context-free palindromes
Viewed 0 times
palindromesfreefirstcontexthalf
Problem
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is context-free, do we always have $L$ is regular?
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is context-free, do we always have $L$ is regular?
Solution
Yes.
Sándor Horváth, J. Karhumäki and H. C. M. Kleijn characterized the context-free languages consisting only of palindromes in their paper Results Concerning Palindromicity, 1987.
Theorem. A context-free language $L\subseteq\Sigma^*$ is palindromic, iff it is of the form
$$ L= \bigcup_{x\in\,\Sigma\cup\{\lambda\}}\{uxu^R : u\in L(x)\}$$
where the $L(x)$ is a regular language uniquely determined by $L$ for all $x \in\Sigma\cup\{\lambda\}$.
In particular, the theorem tells that a context-free languages that consists of only palindromes of even length must be of the form $\{uu^R : u\in L\}$ for some regular language $L$.
Sándor Horváth, J. Karhumäki and H. C. M. Kleijn characterized the context-free languages consisting only of palindromes in their paper Results Concerning Palindromicity, 1987.
Theorem. A context-free language $L\subseteq\Sigma^*$ is palindromic, iff it is of the form
$$ L= \bigcup_{x\in\,\Sigma\cup\{\lambda\}}\{uxu^R : u\in L(x)\}$$
where the $L(x)$ is a regular language uniquely determined by $L$ for all $x \in\Sigma\cup\{\lambda\}$.
In particular, the theorem tells that a context-free languages that consists of only palindromes of even length must be of the form $\{uu^R : u\in L\}$ for some regular language $L$.
Context
StackExchange Computer Science Q#104081, answer score: 4
Revisions (0)
No revisions yet.