How powerful are CFGs that allow an infinite number of rules?

Question

I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ over some alphabet $\Sigma$ could be described by a CFG $G = (\{S\},\Sigma,R,S)$ with $R = \{S \rightarrow w \mid w \in L \}$. But what if we restrict $R$ to such sets of rules that can be created by context free grammars?

For that purpose, given a set of nonterminals $N$ and terminals $\Sigma$, let us view rules not as elements of $N \times (N\cup \Sigma )^*$, but as strings over the alphabet $R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$. Now my question is, if we define an infinite rule CFG to be a tuple $G = (N, \Sigma, R, S)$ where

• $N$ is a finite set of nonterminals
• $\Sigma$ is a finite alphabet
• $R$ is a set of rules of the form $A \rightarrow w$ with $A \in N$, $w \in (N \cup \Sigma)^*$ such that there is some CFG $G'$ over $R_{(N,\Sigma)}$ with $R = L(G')$
• $S \in N$ is the initial nonterminal

and we define $L(G)$ for such infinite rule CFGs just like it is done for CFGs, what is the relation between the class of languages generated by infinite rule CFGs (let's call that class $irCF$), the class of context-free languages $CF$ and the class $RE$?

Obviously, we have $CF \subseteq irCF \subseteq RE$, but is $irCF$ equivalent to one of these classes (or some other class)?

Answer 1

Suppose we take the metagrammar $G'$ and factor it by two-symbol prefixes. In other words, for each $A \in N$ construct $G'_A$, the left-derivative of $G'$ over the string $A \to$. That will produce a (finite) set of (finite) metagrammars, each one producing all the (possibly infinite) productions for some $A \in N$.

Now, construct the grammar $G''$, whose rules are the union of all the rules in the $G'_A$ grammars (with non-terminals renamed to avoid collisions), along with $A \to S_{G'_A}$ for each $G'_A$, where $S_{G'_A}$ is the start non-terminal for $G'_A$. The non-terminals for $G''$ include $N$ and all the non-terminals for each $G'_A$; the start non-terminal is the start non-terminal of $G$, and the terminals for $G''$ are precisely the terminals for $G$. I assert (without proof) that $G''$ is a finite grammar for the same language, since the derivation process isn't affected by the origin of the rules; it is just a string substitution over an alphabet.

If the above proof outline is valid, $CF$ and $irCF$ are the same.

As I alluded in a comment, there are more interesting examples of two-level grammars, including Van Wijngaarden grammars and the various attempts which have been made to create more manageable formalisms without losing all of the additional power.