First half of context-free palindromes

Question

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?

Answer 1

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$.

Answer 2

I believe the answer should be affirmative. Here are some ideas on how to prove this.

We can remove from the grammar any nonterminals which are unreachable or produce only finite languages (we can assume that $L$ itself is infinite). Now suppose that $S \Rightarrow^* xAy$. If $|x| = |y|$, then $x = y^R$ and $L(A) \subseteq \mathsf{PAL}$, where $\mathsf{PAL}$ is the language of all palindromes. If $|x| > |y|$ then $x = y^R z$, and then $L(A)z^R \subseteq \mathsf{PAL}$. Similarly, when $|x| < |y|$ there is a word $w$ such that $wL(A) \subseteq \mathsf{PAL}$.

Now suppose $A \Rightarrow^* xAy$. We want to understand what happens when $|x| \neq |y|$, say $|x| > |y|$. We will only consider the case $L(A) \subseteq \mathsf{PAL}$, but the others should be similar. Suppose $A \Rightarrow^* w$. Thus $x^\ell w y^\ell = \bar{y}^\ell \bar{w} \bar{x}^\ell$ for all $\ell$ (we use $\bar{w}$ to denote the reversal of $w$). By considering large enough $\ell$, we can find $I,J$ such that $x^I = \bar{y}^J$, and so $x,\bar{y}$ are powers of the same word $z$, say $x = z^i$ and $y = \bar{z}^j$. Using $k = i-j$, this means that $$ z^{\ell i} w \bar{z}^{\ell j} = z^{\ell j} \bar{w} \bar{z}^{\ell i} \longrightarrow z^{\ell k} w = \bar{w} \bar{z}^{\ell k}. $$ Thus we can write $\bar{w} = z^r s$, where $z = st$. This gives $$ t z^{\ell k-r-1} = \bar{z}^{\ell k-r-1} \bar{t} \longrightarrow t(st)^{\ell k-r-1} = (\bar{t}\bar{s})^{\ell k-r-1} \bar{t} = \bar{t} (\bar{s}\bar{t})^{\ell k-r-1}, $$ that is, $s$ and $t$ are palindromes. This kind of structure must hold for every $w$ generated by $A$, and we conclude that $L(A) \subseteq \bigcup_s z^* s$, where $s$ goes over all decompositions $z = st$ with $s,t \in \mathsf{PAL}$. This should imply that $L(A)$ is, in fact, regular (via Parikh's theorem).

A similar argument shows that if a production for $A$ has two nonterminals on the righthand side, then $L(A)$ is regular. Therefore we have some regular nonterminals, and the other nonterminals only participate in productions of the form $A \to xB$, $A \to Cy$, and $A \to z$. We can also convert the productions involving regular nonterminals to this form.

Consider now a derivation starting at $S$. In order to simulate its first half using an automaton, we can try the following strategy. We will be reading the complete word (both halves) from both directions at once. If the left pointer has advanced $i$ steps and the right pointer $j$ steps, then we want to have read from the input the first $\min(i,j)$ symbols. We can implement this in a finite automaton as long as $|i-j|$ is bounded (we have to store in memory this many symbols, or at least their count).

If $|i-j|$ is not bounded, then by the pigeonhole principle our derivation contains subderivations of the form $A \Rightarrow^* xAy$ with $\bigl| |x|-|y| \bigr|$ unbounded. As pointed out above, this can happen only for the regular nonterminals, but by setting up the productions correctly, we can ensure that this doesn't happen.

While the ideas above are somewhat sketchy, I believe that they can probably be fleshed out to prove Hendrik Jan's conjecture.

Answer 3

Consider a context-free grammar that generates only palindromes. What do its right hand sides look like? Each can contain only one nonterminal that generates a language with size > 1; so we can expand all other nonterminals away to produce a grammar with only right hand sides with at most one nonterminal. Each of these generates a language of the form $w_1. L. w_2$ where $L$ is a language of palindromes, and $w_1, w_2$ are terminal strings at least one of which is empty.

At this point I'll do some handwaving and say that such a grammar can be normalized into a linear grammar in which all right hand sides are palindromes.

Halve all right hand sides of this grammar to obtain a regular grammar for the halves of its words.