Context-free languages, coalgebraically (2011)

Titel Context-free languages, coalgebraically
Gepubliceerd in Software Engineering [SEN], No. SEN-1101. ISSN 1386-369x.
Auteur Winter, J.; Bonsangue, M.M.; Rutten, J.J.M.M.
Datum 2011-03-01
Trefwoord(en) Coalgebra, context-free grammars, context-free languages
Taal Engels
Type Rapport
Uitgever CWI
Samenvatting 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.
Persistent Identifier urn:NBN:nl:ui:18-18032
Metadata XML
Bron CWI

Ga terug naar de inhoud
Ga terug naar de site navigatie