There was a link to the Wikipedia article on the Dyck language [1] somewhere, which lead me to the Chomsky–Schützenberger representation theorem [2], which says that every context-free language can be represented by a homomorphism applied to the intersection of a Dyck language (possibly with multiple different kinds of parentheses) with a regular language.

The Dyck language can be recognized by a monoid as described. The regular language can be recognized by a monoid whose elements are functions between states of the recognizing automaton, each symbol being identified with the transitions the automaton performs when reading the symbol. The intersection should be describable by the product of monoids. (If such a thing exists, anyway. My abstract algebra is a bit rusty.)

The hard part is dealing with the homomorphism that turns the intersection of the two languages into the context-free language. I'm guessing that the general construction might require turning parentheses into empty strings, which would destroy the simplicity of the monoidal construction.

Anyway, I'm unfortunately not excited enough to see whether I can get it to work, at least not right now. But maybe it helps point someone else in the right direction.

[1] https://en.wikipedia.org/wiki/Dyck_language [2] https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenb...