# Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?

### Definitions

Let $$G$$ be a context free grammar over an alphabet $$\Sigma$$ with non-terminals $$V$$.

• Define the locality $$l(G)$$ as the length of the longest word in $$(V \cup \Sigma)^*$$ that has a derivation tree in $$G$$ where no path contains the same non-terminal symbol twice. Since $$V$$ is finite, this number exists for every grammar $$G$$.

• Define the locality $$l(L)$$ of a language $$L$$ as the smallest value $$l(G)$$ for any grammar $$G$$ with $$L(G) = L$$, or $$\infty$$ if such a number does not exist. (Clearly, a language is context free if and only if such a number exists)

• For a language $$L$$ and $$N \subseteq \mathbb{N} \ni 0$$, define $$L^{\cap N} := \{ w \in L \; | \; |w| \in N \}$$ as the set of words in $$L$$ whose lengths are in $$N$$.

• For a number $$n$$, define $$P_n := \{ w \in \Sigma^* \; | \; \forall v \in \Sigma^*: v^n \neq w \}$$ as the set of words that are not the $$n$$th power of another word.

### Locality Upper Bound

We can show that $$P_n = \{ w \in \Sigma^* \; | \; |w| \not\in n\mathbb{N} \lor \exists i: w_i \neq w_{i+|w|/n} \}$$.

With this insight, it is easy to show that $$P_n$$ is context free for all numbers $$n$$. (Ensure that every word $$w$$ has the form $$w = xaybz$$ for different characters $$a$$ and $$b$$ and $$(n - 1) \cdot |y| + (n - 2) = |xz|$$. To extend the word, add an arbitrary character to $$y$$ and $$n - 1$$ times many arbitrary characters to either $$x$$ or $$z$$. This can easily be implemented as CFG)

The locality of this grammar is less than $$2 \cdot n$$, which establishes an upper bound for $$l(P_n)$$.

### Locality Lower Bound

Because $$0^k \in P_n$$ for $$k \not\in n\mathbb{N}$$, we can show that the locality of $$P_n$$ is at least $$n$$, by pumping that word into $$(\Sigma^*)^{\cap n\mathbb{N}}$$ (as described here). Unfortunately, this argument does not yield much insight and breaks for reasoning about the locality of $$P_n \setminus (0^* | 1^*)$$.

### Open (?) Conjectures

1. Let $$L$$ be a language with $$L^{\cap \{500\}} = P_5^{\cap \{500\}}$$. Then $$l(L) \geq 5$$.

I would find it equally interesting to see a proof or a counter-example of this very concrete conjecture. Intuitively it feels impossible that a grammar with a locality of 4 or less can check if there exists a position $$i$$ such that $$w_i \neq w_{i+100}$$ (assuming the word-length is 500). As $$L$$ could be finite, pumping arguments don't work directly.

1. $$l(P_n \setminus (0^* | 1^*)) \geq n$$

I believe this to be true and hope to find a more insightful argument than used for showing that $$l(P_n) \geq n$$.

1. For a prime number $$p$$, let $$L$$ be a language with $$L^{\cap \{p^k \; | \;k \in \mathbb{N} \}} = P_p^{\cap \{p^k \; | \;k \in \mathbb{N} \}}$$. Then $$l(L) \geq p$$.

This conjecture would imply that the set of primitive words $$Q$$ has an infinite locality, i.e. is not context free, as $$L$$ in this conjecture can be instantiated with $$Q$$ for every $$k$$.

I consider this SE question answered when at least one of those conjectures has been proven or disproven, as they are all related.