Context-Free Languages, Coalgebraically
Context-Free Languages, Coalgebraically
复制标题
代数上的上下文无关语言
DOI：
10.1007/978-3-642-22944-2_25
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Rutten
中科院分区：
文献类型：
--
作者：
Joost Winter;M. Bonsangue;J. Rutten
我们使用字母表 A 上的确定性自动机的函子 D(X) = 2 × XA 给出了上下文无关语言的联合代数描述，以三种不同但等效的方式：（i）将上下文无关语法视为 D-代数； (ii) 通过定义行为微分方程（w.r.t. D）的格式，其唯一解正是上下文无关语言； (iii) 作为广义正则表达式的 D-代数，其中 Kleene 星被唯一的定点运算符替换。在所有情况下，语义都是由所有语言的最终余代数中唯一的同态来定义的，为上下文无关语言等价的共归纳证明铺平了道路。此外，这三个特征可以作为定义上下文无关的一般代数概念的基础，我们将其视为本研究的最终长期目标。
We give a coalgebraic account of context-free languages using the functor D(X) = 2 × XA for deterministic automata over an alphabet A, in three different but equivalent ways: (i) by viewing context-free grammars as D-coalgebras; (ii) by defining a format for behavioural differential equations (w.r.t. D) for which the unique solutions are precisely the context-free languages; and (iii) as the 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, paving the way for coinductive proofs of context-free language equivalence. Furthermore, the three characterizations 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.