# #StackBounty: #fl.formal-languages #context-free Context Free Grammar For Complement Of { www | … } with minimal pumping length?

### Bounty: 150

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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.