5
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lamine
    Apr 29 at 14:56
  • $\begingroup$ Thanks! I think you're right. I will edit the question with a better example, and hopefully still be able to prove the theorem. $\endgroup$
    – user326210
    Apr 30 at 7:42
  • $\begingroup$ cs.stackexchange.com/q/151275/755 $\endgroup$
    – D.W.
    May 7 at 1:44
  • $\begingroup$ @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^*$. $\endgroup$
    – user326210
    May 7 at 21:57
  • 3
    $\begingroup$ 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? $\endgroup$
    – a3nm
    May 10 at 9:12

1 Answer 1

2
$\begingroup$

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.

Thus, this refutes the conjecture.

$\endgroup$

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.