# What is the cardinality of the set of regular grammars?

What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal way, but what I mean is that the actual symbols are arbitrary to me.

So for example the grammar with: {N={α}, Σ={x}, P={α→x}, S=α}

Is equivalent to the grammar: {N={β}, Σ={y}, P={β→y}, S=β}

Hopefully I am being understood! I believe this set is countable because for every N and Σ there are only a finite number of production rules which can be formulated. For example, for:

N={α} and Σ={x}

The only unique sets of production rules are:

{{α→x}}

{{α→xα}}

{{α→x}, {α→xα}}

• It is not clear to me what you mean by "structurally different", but I don't think it matters. – Raphael Jun 9 '16 at 19:48

1. The lower bounds follows from $\{a\}^n$ being regular for every $n \in \mathbb{N}$.