1
$\begingroup$

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?

$\endgroup$
2

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.