| 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. |
| Publicatie | https://repository.cwi.nl/noauth/search/fullrecord.php?publn... |
| Persistent Identifier | urn:NBN:nl:ui:18-18032 |
| Metadata | XML |
| Repository | NWO |
Omhoog
Ga terug naar de inhoud
Ga terug naar de site navigatie