Publicatie

# Context-free languages, coalgebraically (2011) Open access

Pagina-navigatie:
Titel Context-free languages, coalgebraically Software Engineering [SEN], No. SEN-1101. ISSN 1386-369x. Winter, J.; Bonsangue, M.M.; Rutten, J.J.M.M. 2011-03-01 Coalgebra, context-free grammars, context-free languages Engels Rapport CWI We give a coalgebraic account of context-free languages using the functor ${\cal D}(X) = 2 \times X^A$ for deterministic automata over an alphabet $A$, in three different but equivalent ways: (i) by viewing context-free grammars as ${\cal D}$-coalgebras; (ii) by defining a format for behavioural differential equations (w.r.t. ${\cal D}$) for which the unique solutions are precisely the context-free languages; and (iii) as the ${\cal D}$-coalgebra of generalized regular expressions in which the Kleene star is replaced by a unique fixed point operator. In all cases, semantics is defined by the unique homomorphism into the final coalgebra of all languages, thus paving the way for coinductive proofs of context-free language equivalence. Furthermore, the three characterizations are elementary to the extent that they can serve as the basis for the definition of a general coalgebraic notion of context-freeness, which we see as the ultimate long-term goal of the present study. https://repository.cwi.nl/noauth/search/fullrecord.php?publn... urn:NBN:nl:ui:18-18032 XML CWI