Context-free grammars and finite-state automata over categories
Noam Zeilberger
École Polytechnique
Abstract:
Around two years ago, Paul-André Melliès and I wrote a paper giving a
categorical analysis of the so-called Chomsky–Schützenberger
representation theorem, whose usual formulation states that "a
language is context-free iff it is a homomorphic image of the
intersection of a Dyck language with a regular language". Since then,
our understanding of the material has evolved significantly, and we
wrote a thoroughly revised and expanded version of the paper:
The categorical contours of the Chomsky-Schützenberger representation theorem,
https://inria.hal.science/hal-04399404
The main message of the paper is that there are natural notions of
"context-free grammar" and of "non-deterministic finite state
automaton" over arbitrary categories and operads, and that looking at
CFGs and NDFAs in this way seems to have some real explanatory power.
In the talk I will give some examples, and sketch some of the other
ideas and results from the paper.