Context-free languages, coalgebraically
Joost de Winter, Marcello Bonsangue, Jan Rutten · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2011
Abstract. We give a coalgebraic account of context-free languages using the functor D(X) = 2 ×XA for deterministic automata over an alpha-bet A, in three different but equivalent ways: (i) by viewing context-free grammars as D-coalgebras; (ii) by defining a format for behavioural dif-ferential equations (w.r.t. D) for which the unique solutions are precisely the context-free languages; and (iii) as theD-coalgebra of generalized reg-ular expressions in which the Kleene star is replaced by a unique fixed point operator. In all cases, semantics is defined by the unique homo-morphism into the final coalgebra of all languages, paving the way for coinductive proofs of context-free language equivalence. Furthermore, the three characterizations can serve as the basis for the definition of a gen-eral coalgebraic notion of context-freeness, which we see as the ultimate long-term goal of the present study. 1