# Establishing competing memory limits for pushdown automata

Let $$L$$ be the language of all even-length strings whose first half is a palindrome.

Let $$L$$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $$\mathtt{a}$$'s and $$\mathtt{b}$$'s. I believe $$L$$ is not context-free; the intuition is that the equipment of a PDA can either be used to keep both halves of the string the same length, or to construct complex internal structure like a palindrome or an imbalanced string, but not both simultaneously.

I would like to formalize this intuition as a general conjecture, beyond this particular example $$L$$. I suggest that, letting $$A\bowtie B$$ denote the language $$\{xy : x\in A,\;y\in B,\; |x|=|y|\}$$,

Conjecture: $$A\bowtie \Sigma^*$$ is context free if and only if $$A$$ is regular.

This conjecture would then establish that $$L\equiv \mathsf{imbalanced}\bowtie \Sigma^*$$ isn't context-free. One direction $$(\Leftarrow)$$ is easy, using regular grammars. But I wonder if anyone knows or can see a proof of the other direction?

Is a proof of this statement already well known or easily constructible?

Maybe it would be easier to prove this more broadly:

Conjecture: If $$A\bowtie B$$ is context free and $$A$$ and $$B$$ have the same word sizes $$\{|x| : x\in A\} = \{|y| : y \in B\}$$, then $$A$$ and $$B$$ are regular.

So far I have tried arguing about the derivation tree for $$A\bowtie \Sigma^*$$, considering cases of which parentheses are allowed on which halves of the string in the Chomsky Schuetzenberger theorem, limiting to the case where $$A$$ and $$\Sigma^*$$ have different(-colored) alphabets, and similar. I have proved it for the case where the alphabets of $$A$$ and $$B$$ are disjoint (e.g. color-coded), by arguing about the cases of colors of strings that the nonterminals of a grammar for $$A\bowtie B$$ can produce in CNF.

Edit: Having looked at generating functions, I know that if $$A(x)$$ is the generating function for strings of each length $$n$$ in $$A$$, then $$A(2x^2)$$ is the generating function for $$A\bowtie \Sigma^*$$, and I know that regular grammars correspond to rational generating functions, unambiguous context-free grammars have algebraic generating functions, and $$\bowtie$$ corresponds to the Hadamard product, which has certain closure properties relative to rational and algebraic functions—but since I don't know a characterization of what kind of context-free languages $$A\bowtie B$$ can be, I don't see what to uncover next.

• Maybe I'm mistaken, but it seems to me that the first language can be proven not CFL using the pumping lemma. Take the words $s=uvwxy=a^Nba^Nb^{2N+1}$. Since $|vwx|\leq N$. By pumping, the palindrome is always destroyed. Apr 29 at 14:56
• Thanks! I think you're right. I will edit the question with a better example, and hopefully still be able to prove the theorem. Apr 30 at 7:42
• cs.stackexchange.com/q/151275/755
– D.W.
May 7 at 1:44
• @D.W. Useful reference to show that the conjecture for $A\bowtie B$ doesn't hold for arbitrary $B$. I wonder if there's a way to apply that reasoning to the original conjecture about $A\bowtie \Sigma^*$. May 7 at 21:57
• On alphabet $\Sigma = \{0, 1\}$, isn't the language $\{0^n 1 (0|1)^{3n+1} | n > 0\}$ context-free, for the same reason that $\{0^n 1^{3n} | n > 0\}$ from the CS.SE question is? If so, doesn't this refute your claim because $A = \{0^n 1 (0|1)^n | n > 0\}$ is context-free but not regular?
– a3nm
May 10 at 9:12

This answer is inspired by this question. The conjecture is false, for the following reason. Consider the alphabet $$\Sigma=\{0,1\}$$, and the language $$A=\{0^n1(0|1)^n|n>0\}$$. This language is context-free but not regular.
Now, $$A \bowtie \Sigma^*$$ is the language $$\{0^n 1 (0|1)^{3n+1}|n>0\}$$. This language is context-free, for the same reason as the language $$\{0^n 1^{3n}|n>0\}$$ from the question mentioned before.