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.

  • $\begingroup$ Please, if someone downvotes, it is welcome a comment to allow improve the question or to withdraw it in case there are something completly incorrect. $\endgroup$ Dec 7, 2015 at 15:10
  • 1
    $\begingroup$ I'm not sure why it was downvoted, maybe someone found the notation confusing. I tried to latexify it, and make it a bit clearer, hopefully the changed version will show up soon. $\endgroup$ Dec 10, 2015 at 17:23
  • $\begingroup$ @Laszlo Kozma: Thanks a lot for the edits. I didn't know I could use $$ in my text. $\endgroup$ Dec 11, 2015 at 12:07

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.