Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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