# Conjecture: a half of a pairing context-free language must be a regular language

If $$A$$ and $$B$$ are languages, let $$A\bowtie B$$ denote the set of strings made by concatenating any word from $$A$$ and any word from $$B$$ of equal length.

$$A\bowtie B \equiv \{ ab : a\in A,\;b\in B, |a|=|b|\}.$$

You can prove using regular grammars that if $$A$$ and $$B$$ are regular, then $$A\bowtie B$$ is context free. I am wondering about the converse. Specifically, this conjecture:

Conjecture: If $$A\bowtie B$$ is context-free, and the strings in $$A$$ and $$B$$ have the same lengths $$\{|a| : a\in A\}=\{|b| : b\in B\}$$, then $$A$$ and $$B$$ are regular.

The intuition behind the conjecture is that the pushdown stack can be used to ensure that $$A$$ and $$B$$ are the same length, or to generate complex internal structure within $$A$$ and $$B$$ (such as palindromes or matching character counts) but not both simultaneously.

I haven't been able to prove this, even for the simple case where $$B$$ is the language of all strings. Unfortunately, I've also not been able to find a counterexample.

So far I have tried:

1. Using Parikh's theorem, Odgen's lemma, and the pumping lemma for CFLs.
2. Using generating functions—regular languages have rational gfs and unambiguous cfls have algebraic gfs, but not conversely.
3. Using the Chomsky-Schutzenberger theorem and trying to catalogue parentheses based on whether their image is always in the left/right half of the derived string.
4. Showing that the conjecture holds when the alphabets are distinct. This turns out to be easy to prove (using Chomsky normal form). But I don't have any indication that if $$A\bowtie B$$ is context free then it is also the homomorphic image of a context free language $$A^\prime \bowtie B^\prime$$, where $$A$$ and $$B$$ have distinct alphabets.

• The special case when $B$ is the language of all strings was raised before May 6 at 3:18
• "I am wondering about the converse". Your conjecture is not the exact converse. I would like to suggest that you remove the condition "the strings in $A$ and $B$ have the same lengths $\{|a| : a\in A\}=\{|b| : b\in B\}$" in your conjecture, since that seems an unnecessary condition. Wait, it is necessary... May 6 at 3:41
• @JohnL.: I'm surprised that you've added the open-problem tag. The tag description says it's for "Problems without an answer after substantial efforts by many users. This tag indicates the problem is of graduate research level and beyond"; but you successfully answered the question within two hours of when it was posted, and judging from the lack of comments and other answers, no one else put any effort into this (aside from the OP, of course). May 6 at 22:13
• @ruakh Indeed, I judged the question wrong. I thought this conjecture was a natural generalization of another unsolved conjecture. I should have been more careful. I will remove the tag if the asker does not take action for a while. May 6 at 22:45
• @ruakh Although the explicit question has a definite negative answer, the broader question is what additional conditions (besides equal string lengths) could be added to make the conjecture hold. That may be a valid open question. May 7 at 1:12

Consider $$A=\{0^n1^n \mid n\geqslant0 \}$$ and $$B=\{1^{2n}\mid n\geqslant0\}$$.
We have $$\{|a| : a\in A\}=\{|b| : b\in B\}=\{2n\mid n\geqslant0\}$$ and $$A\bowtie B = \{ 0^n1^{3n}\mid n\geqslant0\}$$.
While $$A\bowtie B$$ is context-free, $$A$$ is not regular.
• Worth noting here that $B$ is regular, and so this example (and various trivial modifications to it) also shows that even if one of $A$ or $B$ is regular, that doesn't mean the other is too. May 6 at 5:00
• @user326210 Interestingly the example has a very specific structure. Both $A$ and $A\bowtie B$ are linear context-free. Also the extra letters to go from strings in $A$ to strings in $A\bowtie B$ are not necessarily added at the right but can be added in between. So we go from $S\to 0S1$ to $S\to 0S111$. Fascinating. May 6 at 18:39