Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.