0
$\begingroup$

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α}}

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

There is at least one regular grammar per regular language, and all of them are pairwise inequivalent (for any meaningful equivalence relation). Since there is at least a countably infinite number of regular languages¹, that's a lower bound for the number of regular grammars as well.

Without loss of generality², you can write down every regular grammar as finite string over a finite alphabet. Therefore, there are at most as many regular grammars as binary strings, of which there are countably infinitely many.

Combine the bounds to get your answer.


  1. The lower bounds follows from $\{a\}^n$ being regular for every $n \in \mathbb{N}$.
  2. Encode all symbols using binary numbers.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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