论文部分内容阅读
自动机理论是计算理论的数学模型,是可计算、算法描述和分析、计算复杂性理论等问题研究的基础.在自动机理论中,一个重要的研究课题是自动机与文法的等价性.在经典自动机理论中,确定型有穷自动机、非确定型有穷自动机与正则文法是等价的.加权有限自动机(WFA)是经典自动机的推广,是在非确定型有穷自动机的转移上附加上表示距离、费用、资源消耗等等的权重后形成的一类新的自动机,这些附加上的权重构成代数结构半环.2011年M Droste, I.Meinecke在半环的基础上进行推广,首次提出赋值幺半群的概念,并在赋值幺半群上对自动机的相关问题进行研究.本文在此基础上研究赋值幺半群上加权自动机与正则文法的等价性问题.我们引入权重取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)之间的关系.主要工作如下:1.给出权重取值于赋值幺半群的加权正则文法、加权类正则文法及可分配的赋值幺半群的概念,研究了加权正则文法和加权自动机(WFA)的等价性.定义了加权正则文法,加权类正则文法,证明了在赋值幺半群上已知一个加权正则文法,存在一个WFA与该加权正则文法生成的语言相等;已知一个加权类正则文法,存在一个WFA与该加权类正则文法生成的语言相等.定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法与该WFA生成的语言相等;已知一个WFA,存在一个加权类正则文法与该WFA生成的语言相等.即可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上是等价的.并分别举例说明了可分配性不是必要条件,即推论2.2.7,推论2.3.4的逆命题不成立.并给出了由加权类正则文法构造与之等价的加权正则文法的方法.2.定义了有单位元的赋值幺半群,并在其基础上定义确定型加权自动机(WDFA)、确定型加权正则文法.通过构造,证明了在有单位元的赋值幺半群上,确定型加权正则文法和WDFA等价.定义确定型加权类正则文法,证明了在有单位元的赋值幺半群上,确定型加权类正则文法和WDFA等价.