#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!!!

Leave a Reply

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