A categorical perspective on context-free grammars and the Chomsky-Schützenberger Theorem

January 16, 2023

Noam Zeilberger (LIX)

I will discuss joint work with Paul-André Melliès in which we analyze context-free grammars as certain kinds of functors of operads, and parsing as a lifting problem [1]. One advantage of this perspective is that it naturally generalizes to enable one to define context-free languages of arrows in any category. Another advantage is that it allows one to study context-free grammars in a common setting with finite state automata, the latter seen as certain kinds of functors of categories. Relying on this (as well as on a surprising adjunction!) we give a categorical reconstruction of (a generalization of) the Chomsky-Schützenberger Representation Theorem, whose classical statement says that any context-free language may be represented as the homomorphic image of the intersection of a Dyck language of balanced parentheses with a regular language.

[1] Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem. MFPS 2022.
https://hal.archives-ouvertes.fr/hal-03702762