# Is there a name for this relation on CFGs?

I'm looking for the name (or a name if there isn't one already) of this relation between $G_1=\left<\Sigma_1,\mathcal{N}_1,\mathcal{R}_1,S_1\right>$ and $G_2=\left<\Sigma_2,\mathcal{N}_2,\mathcal{R}_2,S_2\right>$: $$\exists f_\Sigma\in\Sigma_1\times\Sigma_2,f_\mathcal{N}\in\mathcal{N_1}\times\mathcal{N}_2 \text{ surjective functions s.t. }\\ \mathcal{R}_2=\left\{f_\mathcal{N}(N)\rightarrow f(\alpha)\mid N\rightarrow\alpha\in R_1\right\}\text{ and } S_2=f_\mathcal{N}(S_1)$$ where $f$ is the extension of $f_\Sigma$ and $f_\mathcal{N}$ to words ($f\in(\Sigma_1\cup\mathcal{N}_1)^*\times(\Sigma_2\cup\mathcal{N}_2)^*$).

In other words, you can map $G_1$ to $G_2$ (but not necessarily $G_2$ to $G_1$).

If the mapping function were bijective, this would be an isomorphism, but they're not.

What about if only $f_\mathcal{N}$ is surjective, i.e. $f_\Sigma$ is bijective, or even the identity function?

-

## 1 Answer

This is a kind of (surjective) homomorphism, but the traditional definition is defined only over terminal symbols, not nonterminals.

Your definition would merge unrelated nonterminals from the first grammar with each other in the second grammar, thereby allowing (the image of) unrelated parts of the grammar to get mixed up with each other. This probably does not have nice properties, at least compared to the traditional definition of homomorphism.

That said, I can imagine that it is useful for some kinds of modelling, of AOP, of dynamic binding, of extensible grammars. I'd be interested in knowing what your application is.

-
Your answer made me realise that this property does not really make sense on generic CFGs. I have additional constraints on the grammars which prevent merging completely unrelated rules. Knowing that, I don't think that there's a name for it. Thanks anyway for putting in the time to answer. – Khaur Jan 28 '13 at 16:23