<p>Fix a finite alphabet.</p>
<p>Let <span class="math-container">$\mathrm{CFG}$</span> be the set of context-free grammars on this alphabet, <span class="math-container">$\mathrm{CFL}$</span> the set of context-free languages, <span class="math-container">$\mathrm{UG}$</span> the set of unrestricted grammars and <span class="math-container">$\mathrm{REL}$</span> the set of recursively enumerable languages.</p>
<p>Then we almost have a commutative square <span class="math-container">$\require{AMScd}$</span>
<span class="math-container">\begin{CD}
\mathrm{CFG}\times\mathrm{CFG} @&gt;{?}&gt;&gt; \mathrm{UG}\\
@V{\mathrm{generate}\times\mathrm{generate}}VV @VV{\mathrm{generate}}V\\
\mathrm{CFL}\times\mathrm{CFL} @&gt;{\mathrm{quotient}}&gt;&gt; \mathrm{REL}
\end{CD}</span>
except one map. Is there a natural choice for the missing map?</p>

CC BY-SA 4.0
2021-05-07T14:42:33.537Z
What is the "quotient" map on the bottom of the square?
D.W.
CC BY-SA 4.0
2021-05-07T14:56:58.150Z
@D.W. https://en.wikipedia.org/wiki/Quotient_of_a_formal_language
naloa
<fl.formal-languages><context-free>
Take a natural quotient of context-free grammars
naloa
# Take a natural quotient of context-free grammars

(Asked by: username_0 on 2021-05-07)

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?

**Tags:** fl.formal-languages, context-free
> **Comments:**
> **username_1**: What is the "quotient" map on the bottom of the square?  
> **username_0**: @D.W. https://en.wikipedia.org/wiki/Quotient_of_a_formal_language  

---

## 0 answers

