有限自动机的半群表示

摘要

本文推广了文后参考文献[4]和[5]的一些结果,用自动机的输入半群I及I上的右同余π0构造了一个自动机A（I/π0）=（T/π0,M0,I）,证明循环自动机都同构于这种自动机,进而刻画了自动机的格结构。并且定义了集合N（π0）={y∈I|（x1,x2）∈π0（?）（yx1,yx2）∈π0}。证明了A（I/π0）的自同态都是N（π0）/π0中元素对I/π0的左乘变换。刻画了A（I/π0）的自同态半群和自同构群。使得许多用群来描述自动机的文章所给出的结果成为显然。在中还纠正了[日本]Y. Masunaga等人关于自动机直积分解的一个错误,用半群中的同余关系给出了自动饥直积分解的必要和充分条件。