Context-free languages as models of context-free grammars
Noam Zeilberger
École Polytechnique
Abstract:
In recent work (arXiv:2405.14703), we argued that it was useful to consider context-free grammars fibrationally, and introduced the notion of generalized context-free grammar defined as a functor F S -> O from a free multicategory generated by a finite pointed (colored nonsymmetric) species S into an arbitrary base multicategory
O.
In this talk I want to sketch a still more abstract view of a (generalized) CFG as a kind of "theory" which generates a context-free language as its initial model. One motivation for this perspective is to encompass the old idea of viewing CFLs as minimal solutions to systems of polynomial equations. Analyzing this idea fibrationally we are led to develop some natural mathematical machinery in order to compute the "pushforward" of a model along a translation between grammars, which specializes to the computation of pointwise left Kan extensions along functors of multicategories.
This is based on joint work with Paul-André Melliès (still in progress and hence comments welcome!)