<p>Perhaps I didn't understand the largest minimal pumping length condition correctly, but suppose you have largest minimal pumping length of <span class="math-container">$k=2$</span>.</p>
<p>Then pick a string <span class="math-container">$s = 1^n$</span> with large enough <span class="math-container">$n \mod 3 = 1$</span>;
<span class="math-container">$s \in L$</span> (because <span class="math-container">$n$</span> is not a multiple of <span class="math-container">$3$</span>).</p>
<p>But then you have a pumpable string <span class="math-container">$vw$</span> made only of <span class="math-container">$1$</span>s which has length <span class="math-container">$1$</span> or <span class="math-container">$2$</span>. If it has length 1 then pump <span class="math-container">$X$</span> two more times, if it has length 2 pump <span class="math-container">$X$</span> one more time and you get a string <span class="math-container">$s' = 1^{3m}$</span> which is no more in <span class="math-container">$L$</span>.</p>

CC BY-SA 4.0
2021-07-01T11:04:15.963Z
Very nice, you deserve the bounty! In hindsight very obvious, I did not think about $1^n$ or $0^n$. Now my next question would be to consider the case where $0^*$ and $1^*$ are explicitly removed from the complement so that this argument does not work anymore (and I don't see how it could be repaired). It would be very nice to have an argument that only uses words divisible by 3.
Henning
CC BY-SA 4.0
2021-07-04T16:31:41.693Z
@Henning: I'll think about that case!
Marzio De Biasi
CC BY-SA 4.0
2021-06-30T08:09:59.453Z
2021-06-30T08:09:59.453Z
Marzio De Biasi
<p>Let <span class="math-container">$L := \{ w^3 | w \in \{0,1\}\}^C$</span> be the complement of the language of words that are not the 3rd power of a word over <span class="math-container">$\Sigma = \{0,1\}$</span>.</p>
<p>Let's define the largest minimal pumping length of a grammar <span class="math-container">$G$</span> as the smallest number <span class="math-container">$k$</span>, so that for every non terminal symbol <span class="math-container">$X$</span> where we can derive <span class="math-container">$vXw$</span> for some terminal-words <span class="math-container">$v$</span> and <span class="math-container">$w$</span> with <span class="math-container">$1 \leq |vw|$</span>, we can also derive <span class="math-container">$vXw$</span> with <span class="math-container">$1 \leq |vw| \leq k$</span>.</p>
<p><a href="https://cstheory.stackexchange.com/questions/42194/is-the-complement-of-www-context-free">It is well known that the language <span class="math-container">$L$</span> is context free</a>. (Ensure that there is a substring of length <span class="math-container">$\frac{|v|}{3}+1$</span> whose first and last character differ. To extend <span class="math-container">$v$</span>, this substring can be extended at both ends so that this invariant still holds. These words <span class="math-container">$v$</span> precisely form L when focusing on word-lengths divisible by 3).</p>
<p>However, this grammar for <span class="math-container">$L$</span> has a production of the form <span class="math-container">$X \rightarrow BBXB | 0$</span> and <span class="math-container">$Y \rightarrow BYBB | 1$</span> with <span class="math-container">$B \rightarrow 0|1$</span> (used to extend the substring while maintaining the invariant). Thus, the longest minimal pumping length of this grammar is at least 3.</p>
<p>Is there a grammar for <span class="math-container">$L$</span> that has a largest minimal pumping length of 2?
What about <span class="math-container">$L' := \{w^5 | ... \}^C$</span> - is there a grammar with largest minimal pumping length of 4 or less?</p>
<hr />
<p>It is easy to show that any grammar for the related language <span class="math-container">$\{ 0^{j-1}10^{k-1}10^{2k-j} | j, k \in \mathbb{N}_0, 1 \leq j \leq 2k \}$</span> has a largest minimal pumping length of at least <span class="math-container">$3$</span>.</p>
<hr />
<p>Alternatively, the <em>largest minimal pumping length*</em> for a grammar <span class="math-container">$G$</span> can be defined as the smallest number <span class="math-container">$k$</span> (or <span class="math-container">$\infty$</span> if it does not exist), so that for every non terminal symbol <span class="math-container">$X$</span> where we can derive <span class="math-container">$vXw$</span> for some terminal-words <span class="math-container">$v$</span> and <span class="math-container">$w$</span> with <span class="math-container">$1 \leq |vw|$</span>, we have <span class="math-container">$1 \leq |vw| \leq k$</span> if any <span class="math-container">$X$</span> production is only derived once.
This definition is stronger, but still, the well known grammar <span class="math-container">$G$</span> for <span class="math-container">$L$</span> has a largest minimal pumping length* of 3.</p>

CC BY-SA 4.0
2021-06-20T22:21:27.657Z
If you focus on the simpler language: $L' = L \cap \{ x \mid |x|=3n\}$ (i.e. words of length $3n$ wich are not equal to $w^3$) then having a minimal pumping length of $2$ would probably imply strings out of $L'$ (I should think about it more).
Marzio De Biasi
CC BY-SA 4.0
2021-06-21T06:48:25.470Z
I think so too: If you have a word that is long enough, there must be a non terminal symbol $X$ that is used at least twice in some path on the derivation tree. By assumption, this symbol has a production $X \rightarrow vXw$ with $1 \leq |vw| \leq 2$, so you can derive a word whose length is not divisible by 3. The question is now - how to lift this argument to $L$?
Henning
CC BY-SA 4.0
2021-06-21T07:15:05.937Z
I'll think about it; I'm very interested in the problem because it is related/similar to other small (open) problems that I found on CFGs (see for example [this one](https://cstheory.stackexchange.com/questions/42209/is-ww-hamdistw-w1-context-free)) and clearly it is also related to the BIG open problem of primitive words. Note that in my opinion $L'$ is more "natural" than $L$: in order to achive words of lenght not divisible by 3 you must "add something" to $L'$. In other words if $G$ (resp. $G'$) is the minimal grammar for $L$ (resp. $L'$), then $|G'| < |G|$
Marzio De Biasi
CC BY-SA 4.0
2021-06-21T16:28:15.713Z
This question is indeed very much related to the problem of primitive words: If the minimal pumping length of any language $L$ with $L \cap \{x \;|\; |x| = p^k, k \in \mathbb{N} \} = \{ w^p \;|\; w \in \{ 0, 1 \}^* \}^C $ goes to infinity for primes $p \rightarrow \infty$, then the language of primitive words is not context free.
Henning
CC BY-SA 4.0
2021-06-22T07:07:03.790Z
A doubt: if you intersect (any) $L$ wit the set: $M = \{x \;|\; |x| = p^k, k \in \mathbb{N} \}$ then the result is always different from $T = \{ w^p \;|\; w \in \{ 0, 1 \}^* \}^C$ because for all $p$ the set $T$ contains strings that have length different than $p^k$ ?
Marzio De Biasi
CC BY-SA 4.0
2021-06-22T07:47:58.340Z
@MarzioDeBiasi Sorry, I meant: $L \cap \{ x \; | \; |x|=p^k, k \in \mathbb{N}\} = \{ w^p \; | \; w \in \{0,1\}^∗ \}^C \cap \{ x \; | \; |x|=p^k, k \in \mathbb{N}\}$.

The language of all primitive words has this property for every prime $p$, but it must have a finite minimal pumping length.
Henning
<fl.formal-languages><context-free>
Context Free Grammar For Complement Of { www | ... } with minimal pumping length?
Henning
# Context Free Grammar For Complement Of { www | ... } with minimal pumping length?

(Asked by: username_0 on 2021-06-20)

Let $L := \{ w^3 | w \in \{0,1\}\}^C$ be the complement of the language of words that are not the 3rd power of a word over $\Sigma = \{0,1\}$.

Let's define the largest minimal pumping length of a grammar $G$ as the smallest number $k$, so that for every non terminal symbol $X$ where we can derive $vXw$ for some terminal-words $v$ and $w$ with $1 \leq |vw|$, we can also derive $vXw$ with $1 \leq |vw| \leq k$.

[It is well known that the language $L$ is context free](https://cstheory.stackexchange.com/questions/42194/is-the-complement-of-www-context-free). (Ensure that there is a substring of length $\frac{|v|}{3}+1$ whose first and last character differ. To extend $v$, this substring can be extended at both ends so that this invariant still holds. These words $v$ precisely form L when focusing on word-lengths divisible by 3).

However, this grammar for $L$ has a production of the form $X \rightarrow BBXB | 0$ and $Y \rightarrow BYBB | 1$ with $B \rightarrow 0|1$ (used to extend the substring while maintaining the invariant). Thus, the longest minimal pumping length of this grammar is at least 3.

Is there a grammar for $L$ that has a largest minimal pumping length of 2?
What about $L' := \{w^5 | ... \}^C$ - is there a grammar with largest minimal pumping length of 4 or less?

---

It is easy to show that any grammar for the related language $\{ 0^{j-1}10^{k-1}10^{2k-j} | j, k \in \mathbb{N}\_0, 1 \leq j \leq 2k \}$ has a largest minimal pumping length of at least $3$.

---

Alternatively, the *largest minimal pumping length\** for a grammar $G$ can be defined as the smallest number $k$ (or $\infty$ if it does not exist), so that for every non terminal symbol $X$ where we can derive $vXw$ for some terminal-words $v$ and $w$ with $1 \leq |vw|$, we have $1 \leq |vw| \leq k$ if any $X$ production is only derived once.
This definition is stronger, but still, the well known grammar $G$ for $L$ has a largest minimal pumping length\* of 3.

**Tags:** fl.formal-languages, context-free
> **Comments:**
> **username_1**: If you focus on the simpler language: $L' = L \cap \{ x \mid |x|=3n\}$ (i.e. words of length $3n$ wich are not equal to $w^3$) then having a minimal pumping length of $2$ would probably imply strings out of $L'$ (I should think about it more).  
> **username_0**: I think so too: If you have a word that is long enough, there must be a non terminal symbol $X$ that is used at least twice in some path on the derivation tree. By assumption, this symbol has a production $X \rightarrow vXw$ with $1 \leq |vw| \leq 2$, so you can derive a word whose length is not divisible by 3. The question is now - how to lift this argument to $L$?  
> **username_1**: I'll think about it; I'm very interested in the problem because it is related/similar to other small (open) problems that I found on CFGs (see for example [this one](https://cstheory.stackexchange.com/questions/42209/is-ww-hamdistw-w1-context-free)) and clearly it is also related to the BIG open problem of primitive words. Note that in my opinion $L'$ is more "natural" than $L$: in order to achive words of lenght not divisible by 3 you must "add something" to $L'$. In other words if $G$ (resp. $G'$) is the minimal grammar for $L$ (resp. $L'$), then $|G'| < |G|$  
> **username_0**: This question is indeed very much related to the problem of primitive words: If the minimal pumping length of any language $L$ with $L \cap \{x \;|\; |x| = p^k, k \in \mathbb{N} \} = \{ w^p \;|\; w \in \{ 0, 1 \}^* \}^C $ goes to infinity for primes $p \rightarrow \infty$, then the language of primitive words is not context free.  
> **username_1**: A doubt: if you intersect (any) $L$ wit the set: $M = \{x \;|\; |x| = p^k, k \in \mathbb{N} \}$ then the result is always different from $T = \{ w^p \;|\; w \in \{ 0, 1 \}^* \}^C$ because for all $p$ the set $T$ contains strings that have length different than $p^k$ ?  
> **username_0**: @MarzioDeBiasi Sorry, I meant: $L \cap \{ x \; | \; |x|=p^k, k \in \mathbb{N}\} = \{ w^p \; | \; w \in \{0,1\}^∗ \}^C \cap \{ x \; | \; |x|=p^k, k \in \mathbb{N}\}$.  The language of all primitive words has this property for every prime $p$, but it must have a finite minimal pumping length.  

---

## 1 answers

### Answer by username_1 on 2021-06-30. Score: 2 | Accepted answer

Perhaps I didn't understand the largest minimal pumping length condition correctly, but suppose you have largest minimal pumping length of $k=2$.

Then pick a string $s = 1^n$ with large enough $n \mod 3 = 1$;
$s \in L$ (because $n$ is not a multiple of $3$).

But then you have a pumpable string $vw$ made only of $1$s which has length $1$ or $2$. If it has length 1 then pump $X$ two more times, if it has length 2 pump $X$ one more time and you get a string $s' = 1^{3m}$ which is no more in $L$.

> **Comments:**
> **username_0**: Very nice, you deserve the bounty! In hindsight very obvious, I did not think about $1^n$ or $0^n$. Now my next question would be to consider the case where $0^*$ and $1^*$ are explicitly removed from the complement so that this argument does not work anymore (and I don't see how it could be repaired). It would be very nice to have an argument that only uses words divisible by 3.  
> **username_1**: @Henning: I'll think about that case!  

---

