<p>This answer is inspired by <a href="https://cs.stackexchange.com/q/151275/755">this question</a>. The conjecture is false, for the following reason. Consider the alphabet <span class="math-container">$\Sigma=\{0,1\}$</span>, and the language <span class="math-container">$A=\{0^n1(0|1)^n|n&gt;0\}$</span>. This language is context-free but not regular.</p>
<p>Now, <span class="math-container">$A \bowtie \Sigma^*$</span> is the language <span class="math-container">$\{0^n 1 (0|1)^{3n+1}|n&gt;0\}$</span>. This language is context-free, for the same reason as the language <span class="math-container">$\{0^n 1^{3n}|n&gt;0\}$</span> from the question mentioned before.</p>
<p>Thus, this refutes the conjecture.</p>

CC BY-SA 4.0
2022-05-11T06:52:51.603Z
2022-05-11T06:52:51.603Z
Antoine Amarilli 'a3nm'
<p><strike>Let <span class="math-container">$L$</span> be the language of all even-length strings whose first half is a palindrome.</strike></p>
<p>Let <span class="math-container">$L$</span> be the language of all even length strings whose first half is imbalanced—with an unequal number of <span class="math-container">$\mathtt{a}$</span>'s and <span class="math-container">$\mathtt{b}$</span>'s. I believe <span class="math-container">$L$</span> 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.</p>
<p>I would like to formalize this intuition as a general conjecture, beyond this particular example <span class="math-container">$L$</span>. I suggest that, letting <span class="math-container">$A\bowtie B$</span> denote the language <span class="math-container">$\{xy : x\in A,\;y\in B,\; |x|=|y|\}$</span>,</p>
<blockquote>
<p><strong>Conjecture</strong>: <span class="math-container">$A\bowtie \Sigma^*$</span> is context free if and only if <span class="math-container">$A$</span> is regular.</p>
</blockquote>
<p>This conjecture would then establish that <span class="math-container">$L\equiv \mathsf{imbalanced}\bowtie \Sigma^*$</span> isn't context-free.  One direction <span class="math-container">$(\Leftarrow)$</span> is easy, using regular grammars. But I wonder if anyone knows or can see a proof of the other direction?</p>
<p><strong>Is a proof of this statement already well known or easily constructible?</strong></p>
<hr/>
<p>Maybe it would be easier to prove this more broadly:</p>
<blockquote>
<p><strong>Conjecture</strong>: If <span class="math-container">$A\bowtie B$</span> is context free and  <span class="math-container">$A$</span> and <span class="math-container">$B$</span> have the same word sizes <span class="math-container">$\{|x| : x\in A\} = \{|y| : y \in B\}$</span>, then  <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are regular.</p>
</blockquote>
<p>So far I have tried arguing about the derivation tree for <span class="math-container">$A\bowtie \Sigma^*$</span>, considering cases of which parentheses are allowed on which halves of the string in the Chomsky Schuetzenberger theorem, limiting to the case where <span class="math-container">$A$</span> and <span class="math-container">$\Sigma^*$</span> have different(-colored) alphabets, and similar. I have proved it for the case where the alphabets of <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are disjoint (e.g. color-coded), by arguing about the cases of colors of strings that the nonterminals of a grammar for <span class="math-container">$A\bowtie B$</span> can produce in CNF.</p>
<p>Edit: Having looked at generating functions, I know that if <span class="math-container">$A(x)$</span> is the generating function for strings of each length <span class="math-container">$n$</span> in <span class="math-container">$A$</span>, then <span class="math-container">$A(2x^2)$</span> is the generating function for <span class="math-container">$A\bowtie \Sigma^*$</span>, and I know that regular grammars correspond to rational generating functions, unambiguous context-free grammars have algebraic generating functions, and <span class="math-container">$\bowtie$</span> 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 <span class="math-container">$A\bowtie B$</span> can be, I don't see what to uncover next.</p>

CC BY-SA 4.0
2022-04-29T14:56:58.740Z
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.
Lamine
CC BY-SA 4.0
2022-04-30T07:42:44.800Z
Thanks! I think you're right.  I will edit the question with a better example, and hopefully still be able to prove the theorem.
user326210
CC BY-SA 4.0
2022-05-07T01:44:34.160Z
https://cs.stackexchange.com/q/151275/755
D.W.
CC BY-SA 4.0
2022-05-07T21:57:28.833Z
@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^*$.
user326210
CC BY-SA 4.0
2022-05-10T09:12:47.130Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-05-11T01:10:27.787Z
@a3nm. Yes, that refutes the claim!  The language is context free but its half language is not regular. Thanks very much.
user326210
CC BY-SA 4.0
2022-05-11T06:53:19.870Z
@user326210 sure! I just posted this as an answer to the question to clarify that the problem is settled.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-05-11T19:31:18.780Z
By the way $L$ (first half unbalanced) is context free: just scan the string adding $a$s and subtracting $b$s to/from the stack (or the opposite), and at each position $i$, if the stack is not empty non-deterministically jump to a state that checks that $i$ is exactly half the length of the string (if it is accept, otherwise reject). So this is another proof that the conjecture is false :-)
Marzio De Biasi
<reference-request><fl.formal-languages><context-free><proofs>
Establishing competing memory limits for pushdown automata
user326210
# Establishing competing memory limits for pushdown automata

(Asked by: username_0 on 2022-04-29)

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.

**Tags:** reference-request, fl.formal-languages, context-free, proofs
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks! I think you're right.  I will edit the question with a better example, and hopefully still be able to prove the theorem.  
> **username_2**: https://cs.stackexchange.com/q/151275/755  
> **username_0**: @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^*$.  
> **username_3**: 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?  
> **username_0**: @a3nm. Yes, that refutes the claim!  The language is context free but its half language is not regular. Thanks very much.  
> **username_3**: @user326210 sure! I just posted this as an answer to the question to clarify that the problem is settled.  
> **username_4**: By the way $L$ (first half unbalanced) is context free: just scan the string adding $a$s and subtracting $b$s to/from the stack (or the opposite), and at each position $i$, if the stack is not empty non-deterministically jump to a state that checks that $i$ is exactly half the length of the string (if it is accept, otherwise reject). So this is another proof that the conjecture is false :-)  

---

## 1 answers

### Answer by username_3 on 2022-05-11. Score: 2

This answer is inspired by [this question](https://cs.stackexchange.com/q/151275/755). 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.


---

