<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-07T20:10:12.420Z
2015-12-07T20:10:12.420Z
Klaus Draeger
<p>Let me define the following "grammar":</p>

<p>$$A_0 \leftarrow 1$$</p>

<p>$$A_{i+1} \leftarrow A_i \mid A_i \  K_{i+1} \mid A_i \ K_{i+1} \ A_i$$</p>

<p>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$.</p>

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

<p>My questions are:</p>

<ol>
<li>can I call such a construction a "grammar"?</li>
<li>in which grammar category can I include it?</li>
<li>have such structures been studied before, can anyone give links or bibliographic references?</li>
</ol>

<p>Thanks a lot.</p>

CC BY-SA 3.0
2015-12-07T15:10:52.817Z
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.
pasaba por aqui
CC BY-SA 3.0
2015-12-10T17:23:23.683Z
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.
László Kozma
CC BY-SA 3.0
2015-12-11T12:07:53.743Z
@Laszlo Kozma: Thanks a lot for the edits. I didn't know I could use $$ in my text.
pasaba por aqui
<grammars>
Which kind of grammar is the following?
pasaba por aqui
# Which kind of grammar is the following?

(Asked by: username_0 on 2015-12-07)

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.

**Tags:** grammars

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: @Laszlo Kozma: Thanks a lot for the edits. I didn't know I could use $$ in my text.  

---

## 1 answers

### Answer by username_2 on 2015-12-07. Score: 6

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.


---

