We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
翻译:我们开发了一种完整的图表化方法来应对有限的州自治数据, 其基础是重新将通常的状态- 过渡图形表达方式解释为字符串图的二维语法。 在这种背景下, 我们可以为语言等同提供一个完整的等式理论, 有两个显著的特征。 首先, 拟议的非对称是有限的。 其次, Kleene 恒星是一个衍生的概念, 因为它可以分解成更原始的代数区块 。