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

When a word in $$L(G)$$ that is longer than the locality of $$G$$ is pumped according to the pumping lemma for context free languages, there exists a pumped word that is not longer than the sum of the length of the previous word and the locality of $$G$$. Such a word must have a loop, and extending this loop can only make the word so much longer.

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

• Note that proving 1. is not so easy because the set of primitive words $Q$ is such that: $\forall p,q \text{ primes } Q^{\cap pq}=P_p^{\cap pq}$ . So a "generic" technique for 1. would probably suffice to prove that Q is not CF (which is a long-standing open question). Jan 24, 2023 at 12:17
• I think 1. is a much easier question. If I'm not mistaken, there are only finitely many languages with $l(L) < 5$ and theoretically all these cases could be checked by a computer. Also, your equality is incorrect, otherwise $P_p^{\cap pq} = P_q^{\cap pq}$, which is not the case for $p \neq q$ Jan 25, 2023 at 13:07
• yes you're right, they are not equal, $\forall p,q \text{ primes } Q^{\cap pq}=P_p^{\cap pq} \cup P_q^{\cap pq}$. There are finitely many languages with $l(L) < 5$ and you can check them one by one, but perhaps a more general technique could be applied to the primitive words problem. I'll think more about it. Jan 25, 2023 at 21:10
• I think it should be an intersection, not union, and I think this can be generalized for arbitrary prime factorization. Jan 26, 2023 at 8:34
• I believe it is $Q^{\cap p_1^{v_1} \cdot ... \cdot ... p_n^{v_n} =: k} = P_{p_1}^k \cap ... \cap P^k_{p_n}$ Jan 26, 2023 at 9:52