# Are you allowed to use index variables in grammars?

If we say that the grammar for the language $$L = \{ww \mid w \in \{a,b\}^*\}$$, is:

\begin{align} S &\rightarrow A_1A_2S \mid B_1B_2S \mid Z_2\\ A_2A_1 &\rightarrow A_1A_2\\ A_2B_1 &\rightarrow B_1A_2\\ B_2A_1 &\rightarrow A_1B_2\\ B_2B_1 &\rightarrow B_1B_2\\ A_2Z_2 &\rightarrow Z_2a\\ B_2Z_2 &\rightarrow Z_2b\\ Z_2 &\rightarrow Z_1\\ A_1Z_1 &\rightarrow Z_1a\\ B_1Z_1 &\rightarrow Z_1b\\ Z_1 &\rightarrow \lambda\\ \end{align}

Here, the characters for each word are generated in the order they appear in a word $$x \in L$$ in pairs $$A_1A_2$$ and $$B_1B_2$$, sorted using rules like $$A_2B_1 \rightarrow B_1A_2$$ and then converted with the end character, $$Z_2$$.

It can be seen that we could easily adapt this grammar to recognise the language $$L = \{www \mid w \in \{a,b\}^*\}$$, by changing the start rule to $$S \rightarrow A_1A_2A_3S \mid B_1B_2B_3S \mid Z_3$$ and then adding more sorting and converting rules accordingly.

I am struggling to see how we can generalise this to the language $$L = \{w^i \mid w \in \{a,b\}^*,i \ge 2\}$$, however.

Can you use a rule that looks like $$S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$$, where $$i \ge 2$$?

If so, can we use sorting rules that look like:

$$A_kB_j \rightarrow B_jA_k$$, where $$1 \le j < k \le i$$,

are you allowed to use variables in grammars like that? If so, you could just write the whole grammar as:

\begin{align} S &\rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i,\text{ where } i \ge 2.\\ A_kA_j &\rightarrow A_jA_k;\\ A_kB_j &\rightarrow B_jA_k;\\ B_kA_j &\rightarrow A_jB_k;\\ B_kB_j &\rightarrow B_jB_k,\text{ where } 1 \le j < k \le i.\\ A_kZ_k &\rightarrow Z_ka;\\ B_kZ_k &\rightarrow Z_kb;\\ Z_k &\rightarrow Z_{k-1},\text{ where } 1 \le k \le i.\\ Z_0 &\rightarrow \lambda\\ \end{align}

I have never seen a grammar with variables like this though. But I guess they aren't really variables, because $$i$$ needs to be specified before the computation begins. So, what you would actually be doing is choosing some $$i$$ and then instantiating a version of that grammar, specifially for a given $$i$$. Once the computation has begun, there are no actual variables in the grammar and, effectively, we are just providing rules to build a grammar for the language, based on some $$i$$.

I can think of an algorithm for a Turing machine that could recognise that language (by partitioning the input string $$w$$ in all possible ways such that $$|w|\text{ mod }n = 0$$, where $$n$$ is the number of substrings, and then checking each partition to see if any of them have exactly the same substrings), so the language must be recursively enumerable - I just can't think how to write something like this as a grammar without making rules with variables (if you arent allowed to.. if you are allowed to then I think what I have is okay..)

EDIT:

I think I might have come up with a way of solving the problem without using index variables:

\begin{align} S &\rightarrow LZ_1XR\\ X &\rightarrow A_0X \mid B_0X \mid \lambda\\ Z_1A_0 &\rightarrow A_1A_0Z_1\\ Z_1B_0 &\rightarrow B_1B_0Z_1\\ A_0A_1 &\rightarrow A_1A_0\\ A_0B_1 &\rightarrow B_1A_0\\ B_0A_1 &\rightarrow A_1B_0\\ B_0B_1 &\rightarrow B_1B_0\\ LA_1 &\rightarrow A_1L\\ LB_1 &\rightarrow B_1L\\ Z_1R &\rightarrow RZ_0 \mid Y_0\\ A_0Z_0 &\rightarrow Z_0A_0\\ B_0Z_0 &\rightarrow Z_0B_0\\ LZ_0 &\rightarrow LZ_1\\ A_0Y_0 &\rightarrow Y_0a\\ B_0Y_0 &\rightarrow Y_0b\\ LY_0 &\rightarrow Y_1\\ A_1Y_1 &\rightarrow Y_1a\\ B_1Y_1 &\rightarrow Y_1b\\ Y_1 &\rightarrow \lambda\\ \end{align}

Here, an initial string $$w$$ is generated between $$L$$ and $$R$$ markers using $$A_0$$ and $$B_0$$ non-terminals, then the $$Z_1$$ character is moved to the right of the string, making a copy of the word in $$A_1$$ and $$B_1$$ non-terminals which are then shuffled to the left of the $$L$$ marker, and this process is repeated until you have $$i$$ copies of the string $$w$$, at which point the $$Z_1$$ changes and runs across the string to the left changing all the non-terminals into terminals.

I think this should work fine.. but it is a pretty complicated grammar, so my initial question still remains, are you allowed to use index variables to make rules to generate grammars like I did in the original question?

Can you use a rule that looks like $$S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$$, where $$i \ge 2$$?
No. Grammar rules consist of explicitly given finite strings of terminals and non-terminals on each side of the arrow, and a grammar may contain only finitely many rules. The first restriction rules out the "for all $$i\ge 2$$" part of your rule, and the second part rules out viewing that single rule as standing for the infinite sequence of rules $$A_1\to B_1$$, $$A_1A_2\to B_1B_2$$, $$\dotsc$$.
Note that, if rules are allowed to be infinite (in size or number) then you can write a grammar for every language, as you can just give the infinite rule $$A\to s_1\mid s_2\mid \dots$$.