加权有穷自动机的代数性质*

张丽霞

(安庆师范学院数学与计算科学学院,安徽 安庆 246013)

加权有穷自动机的代数性质*

张丽霞

(安庆师范学院数学与计算科学学院,安徽 安庆 246013)

在加权有穷自动机理论基础上，利用强同态的概念，证明两个加权有穷自动机在计算能力上是等价的，并在加权有穷自动机的状态集上建立一种等价关系，得到加权有穷自动机的商自动机，证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念，讨论在(强)同态的条件下，两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。

形式幂级数；加权有穷自动机；同态；强连通

1 引言

在计算机科学中，自动机作为计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论[1～5]。1961年，Schützenberger M P[6]首先提出了加权自动机的概念，并提出了半环上的形式幂级数的概念，证明了Kleene-Schützenberger 定理，即加权有穷自动机所识别的形式幂级数和有理幂级数是一致的。随后，又有很多学者在这一领域作出了进一步有意义的工作[7～12]。目前，加权自动机在模式识别、模型检测、数字图像压缩算法等领域取得了广泛的应用[13～15]。由于 Successor 和Source 算子是自动机理论中的重要工具之一，Kuroki N、Tiwari S P，Srivastava A K等[16～21]利用 Successor 和 Source算子研究了模糊有穷自动机(强)连通性、分离性、交换等性质，并给出了模糊自动机一些结构刻画。本文将在半环的结构上，研究加权有穷自动机的同态和强同态及其性质，并在加权有穷自动机的状态集上建立一种等价关系，从而得到加权有穷自动机的商自动机。……