8
$\begingroup$

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.

Any advice is appreciated.

$\endgroup$
5
  • 2
    $\begingroup$ The special case when $B$ is the language of all strings was raised before $\endgroup$
    – John L.
    May 6 at 3:18
  • $\begingroup$ "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... $\endgroup$
    – John L.
    May 6 at 3:41
  • $\begingroup$ @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). $\endgroup$
    – ruakh
    May 6 at 22:13
  • $\begingroup$ @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. $\endgroup$
    – John L.
    May 6 at 22:45
  • $\begingroup$ @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. $\endgroup$
    – user326210
    May 7 at 1:12

1 Answer 1

12
$\begingroup$

No, this conjecture is not true.

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – Pseudonym
    May 6 at 5:00
  • $\begingroup$ This is very useful! I wonder if there's a way to strengthen the condition to make the conjecture true? What is it about this example that breaks the assumption? $\endgroup$
    – user326210
    May 6 at 5:12
  • $\begingroup$ @user326210 Please come here for a chat. $\endgroup$
    – John L.
    May 6 at 5:16
  • $\begingroup$ @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. $\endgroup$ May 6 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.