Cheap and Secure Web Hosting Provider : See Now

[Solved]: How powerful are CFGs that allow an infinite number of rules?

, , No Comments
Problem Detail: 

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

Asked By : vauge

Answered By : rici

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback