# Context Free Grammar For Complement Of { www | ... } with minimal pumping length?

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. (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.

• 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). Jun 20, 2021 at 22:21
• 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$? Jun 21, 2021 at 6:48
• 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) 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|$ Jun 21, 2021 at 7:15
• 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. Jun 21, 2021 at 16:28
• 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$ ? Jun 22, 2021 at 7:07

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$$.
• 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. Jul 1, 2021 at 11:04