# Take a natural quotient of context-free grammars

Fix a finite alphabet.

Let $$\mathrm{CFG}$$ be the set of context-free grammars on this alphabet, $$\mathrm{CFL}$$ the set of context-free languages, $$\mathrm{UG}$$ the set of unrestricted grammars and $$\mathrm{REL}$$ the set of recursively enumerable languages.

Then we almost have a commutative square $$\require{AMScd}$$ $$\begin{CD} \mathrm{CFG}\times\mathrm{CFG} @>{?}>> \mathrm{UG}\\ @V{\mathrm{generate}\times\mathrm{generate}}VV @VV{\mathrm{generate}}V\\ \mathrm{CFL}\times\mathrm{CFL} @>{\mathrm{quotient}}>> \mathrm{REL} \end{CD}$$ except one map. Is there a natural choice for the missing map?

• What is the "quotient" map on the bottom of the square? – D.W. May 7 at 14:42
• – naloa May 7 at 14:56