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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.