The problem is to define or prove the impossibility of defining an indexed grammar for the set of strings $A q B$ such that
- $A$ is at least one symbol and does not contain $q$
- $B$ does not contain $q$ and does not contain $A$ as a substring.
(Here I use upper/lower-cased symbols for nonterminals/terminals respectively.)
I suspect it is impossible to define such a grammar, but I can't think of how to prove it.
What I believe I have, is an indexed grammar for a strict subset of the above language that adds the constraint that $A$ must contain $i$ exactly once and as a prefix. Let $T=F∪\{ q, i \}$ where $T$ is the alphabet and $F$ the set of index symbols. $S$ is the starting nonterminal. The productions are:
- $\forall x\in F: S[\sigma] \to S[x\sigma]$
- $S[\sigma] \to A[\sigma] q B[\sigma]$
- $A[\sigma] \to i \sigma$
- $B[\sigma] \to H J[\sigma]$
- $H \to \epsilon$
- $\forall x\in F: H \to x H$
- $J[\sigma] \to \epsilon\,|\,i N[\sigma] J[\sigma]$
- $\forall x\in F: N[x\sigma] \to \epsilon\,|\,x N[\sigma]$
- $\forall x\in F, y\in F, x\neq y: N[x\sigma] \to y H$