论文部分内容阅读
加权有穷自动机是经典的非确定有穷自动机的转移附加上权重,这些权重通常做成一个代数结构-半环.取值于半环的加权有穷自动机的理论研究及其实际应用都已经得到了很好的阐述.最近,不少作者发现自动机的权重可以作成更广泛的代数结构-伪半环(也叫做强双半群),即半环去掉分配律形成的代数结构.半环、格半群、完备正交模格都是伪半环的特例.Manfred Droste教授在他的两篇文章中给出了三种语义下伪加权有穷自动机(也称作强双半群上的加权有穷自动机,简记为P-NFA)所识别的语言,并分别研究了伪加权有穷自动机的一些性质及其确定化.本文进一步研究伪加权有穷自动机的其它性质.本文的主要工作主要有以下几个方面：(1)在七种不同语义下,研究了各类型的伪加权有穷自动机的关系.首先介绍了偏序伪半环、正序伪半环、伪加权子集、伪加权矩阵的概念.其次,论文在已有的三种语义基础上增加了四种新的语义,得到了七种语义,它们分别是初始代数语义(I)、终止代数语义(F)、初始转移语义(IT)、终止转移语义(FT)、初始混合语义(IH)、终止混合语义(FH)、运行语义(R).引入了左等价、右等价、M-右等价、等价、右等价-、M-右等价-ε、等价-ε的概念(其中,φ≠M∈{I,F,IT,FT,TH,R}),利用这些概念,在七种语义下详细讨论了四类型非确定型伪加权有穷自动机P-NFA1,P-FA2,P-FA3,P-FA4之间的关系,以及三类型确定型伪加权有穷自动机P-DFA1,P-FA2,P-FA3之间的关系.得到了完整的结论.最后,介绍了七种语义下伪加权有穷自动机的反转的一些性质.(2)研究了几类带有输出的伪加权有穷自动机的性质.文章给出了几种常见的带输出的伪加权有穷自动机,它们分别是：伪加权转换器、伪加权同步机、伪加权序列机、伪加权Mealy机、伪加权Moore机.并给出了伪加权转换器的延迟函数的实现化、伪加权转换器的输出函数及输入函数的实现化、伪加权转换器的极小确定实现化、伪加权同步机的单转移实现化；借助于伪加权序列机,证明了伪加权Mealy机与伪加权Moore机是不等价的.(3)研究了伪加权图灵机的一些性质.在深度优先和宽度优先意义下,首先讨论了非确定型伪加权图灵机P-TM与带有分明移动的伪加权图灵机P-TMc的关系、带有分明移动的伪加权图灵机P-TMc与确定型伪加权图灵机P-DTM的关系.证明了P-TM与P-TMc不论在深度优先还是在宽度优先意义下都是不等价的,但P是乘法局部有限时二者在深度优先意义下是等价的；P-TMc与P-DTM也是不等价的,甚至在P是加法局部有限时,二者也不等价,但当P是偏序伪半环时,作为有限伪加权递归语言的识别器二者又是等价的.其次讨论了伪加权图灵机的通用性.证明了在P有限时,通用P-TM(P-TMc)与通用P-DTM都是存在的；当伪半环P无限时,通用P-DTM不存在.