Which kind of grammar is the following?

Question

Let me define the following "grammar":

$$A_0 \leftarrow 1$$

$$A_{i+1} \leftarrow A_i \mid A_i \ K_{i+1} \mid A_i \ K_{i+1} \ A_i$$

where $1$ and $K_i$ are terminals (infinite amount of them: $K_1, K_2, \dots$ ), $A_0, A_1, \dots$ are non-terminals, $\mid$ means alternative, $\leftarrow$ defines a non-terminal, $i$ is an integer such that $i \geq 0$.

That is, it looks like a grammar composed of an infinite number of rules and terminals.

My questions are:

1. can I call such a construction a "grammar"?
2. in which grammar category can I include it?
3. have such structures been studied before, can anyone give links or bibliographic references?

Thanks a lot.

Answer 1

The simple answer would be that, having an infinite set of rules, this is not a grammar in the usual sense. Languages over infinite alphabets have been investigated, but usually using register automata rather than grammars.

That being said, you could treat the language as a limit (i.e. infinite union) of finitary languages defined by the "truncations" $G_i$ which you obtain by omitting all indices greater than $i$. I am unfortunately not familiar with research into such beasts.