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)?


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


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.