6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$
    – Marzio De Biasi
    Jun 20, 2021 at 22:21
  • $\begingroup$ 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$? $\endgroup$
    – Henning
    Jun 21, 2021 at 6:48
  • $\begingroup$ 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|$ $\endgroup$
    – Marzio De Biasi
    Jun 21, 2021 at 7:15
  • $\begingroup$ 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. $\endgroup$
    – Henning
    Jun 21, 2021 at 16:28
  • $\begingroup$ 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$ ? $\endgroup$
    – Marzio De Biasi
    Jun 22, 2021 at 7:07

1 Answer 1

Reset to default
2
+150
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Henning
    Jul 1, 2021 at 11:04
  • $\begingroup$ @Henning: I'll think about that case! $\endgroup$
    – Marzio De Biasi
    Jul 4, 2021 at 16:31

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.