In this article, we provide a coalgebraic account of parts of the mathematical theory underlying context-free languages. We characterize context-free languages, and power series and streams generalizing or corresponding to the context-free languages, by means of systems of behavioural differential equations; and prove a number of results, some of which are new, and some of which are new proofs of existing theorems, using the techniques of bisimulation and bisimulation up to linear combinations. Furthermore, we establish a link between automatic sequences and these systems of equations, allowing us to, given an automaton generating an automatic sequence, easily construct a system of behavioural differential equations yielding this sequence as a context-free stream.
Additional Metadata
Keywords coalgebra, context-free languages, formal power series, automatic sequences, counting function
ACM Formal Definitions and Theory (acm D.3.1), Formal Languages (acm F.4.3)
THEME Software (theme 1)
Publisher CWI
Series Software analysis and transformation [SwAT]
Citation
Winter, J, Bonsangue, M.M, & Rutten, J.J.M.M. (2013). Context-free Coalgebras. Software analysis and transformation [SwAT]. CWI.