| Summary: | In this article, we provide three coalgebraic characterizations of the class
of context-free languages, each based on the idea of adding coalgebraic
structure to an existing algebraic structure by specifying output-derivative
pairs. Final coalgebra semantics then gives an interpretation function into the
final coalgebra of all languages with the usual output and derivative
operations. The first characterization is based on systems, where each
derivative is given as a finite language over the set of nonterminals; the
second characterization on systems where derivatives are given as elements of a
term-algebra; and the third characterization is based on adding coalgebraic
structure to a class of closed (unique) fixed point expressions. We prove
equivalences between these characterizations, discuss the generalization from
languages to formal power series, as well as the relationship to the
generalized powerset construction.
|
|---|