取值于赋值幺半群的加权正则文法语言研究

《取值于赋值幺半群的加权正则文法语言研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号ＴＰ３０１．１密级公开学号１３１４８３圓ｉＴｕＴＢＭＩｌＷ擺ｆｉ墨ｉＳａａ硕±学位论文（学术型）题目取值于赋值么半群的加权正则文法语言研究作者？指导教师李永明教授—级学科名称数学二级学科名称基础数学提交日期二〇—六年丑月陕西师范大学学位论文独创性声明本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果．尽我所知除文中已经注明引用的内容外论文中不包含其他个人已经发表，，或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位或证书

2、而使用过的材料．对本文的研究做出重要贡献的个人和集体均己在文中作了明确说，明并表示谢意．—作者签名日期：乂陕西师范大学学位论文使用授权声明本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大学．本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师范大学．学校有权保留学位论文并向国家主管部口或其它指定机构送交论文的电子版和纸质脱有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索：有权将学位论文的标题和摘要汇编出版．乂．

3、作者签名：養命日期；，摘要自动机理论是计算理论的数学模型是可计算、算法描述和分析、计算复杂性理论等问题研，一充的基础．在自动机理论中个重要的研巧课题是自动机与文法的等价性．在经典自动机理论，中确定型有穷自动机、非确定型有穷自动机与正则文法是等价的．加权有限自动机（ＷＦＡ，是）经典自动机的推广在非确定型有巧自动机的转巧上附加上表示距离、费用、资源消耗等，是一等的权重后形成的类新的自动机．２０１１．Ｄ，这些附加上的权重构成代数结构半环年Ｍｒｏｓｔｅ，Ｉ．Ｍｅｉｎｅｃｋｅ在半环的基础上进行推广首次提出赋值么半群的概念并在赋值么半群

4、上对自动，，机的相关问题进行研充．本文在此基础上研究赋值么半群上加权自动机与正则文法的等价性问题．我们引入权重取值于赋值么半群的加权正则文法、加权类正则文法的定义讨论了赋值么半群上加权正则文法、，加权类正则文法和加权有限自动机（ＷＦＡ）之间的关系．主要工作如下：１．给出权重取值于赋值么半群的加权正则文法、加权类正则文法及可分配的赋值么半群的概念研巧了加权正则文法和加权自动机ＷＦＡ的等价化定义了加权正则文法加权类正，（），一则文法证明了在赋值么半群上己知个加权正则文法在一个ＷＦＡ与该加权正则文法生成，，存的语言相等已知一个加权

5、类正则文法一ＦＡ与该加权类正则文法生成的语言相．；在，存个Ｗ等定义了可分配的赋值么半群证明了在可分配的賦值么半群上己知一个ＷＦＡ存在一个加权正，，一则文法与该ＷＦＡ生成的语言相等已知个ＷＦＡ在一个加权类正则文法与设ＷＦＡ生成；，存的语言相等．即可分配的赋值么半群上加权正则文法、加权类正则文法和ＷＦＡ在生成语言上是等价的．并分别举例说明了可分配性不是必要条件２即推论．２．７推论２．义４的逆命题不成，，立．并给出／由加权类正则文法构造与之等价的加权正则文法的方法．２．定义了有单位元的赋值么半群并在其基础上定义确定型加权自动机ＷＤＦＡ、确

6、，（）定型加权正则文法．通过构造证明了在有单位元的赋值么半群上确定型加权正则文法，，和ＷＤＦＡ等价．定义确定型加权类正则文法证明了在有单位元的賦值么半群上确定型加，，权类正则文法和ＷＤＦＡ等价．关键卸赋值么半群加权自动化加权正则文法确定型加权自动化确定型，，加权正则文法ＩＡｂｓｔｒａｃｔＡｕｔｏｍａｔａｔｈｅｏｒｙｉｓａｓｉｍｐｌｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆｃｏｍｐｕｔａｔｉｏ打ｔｈｅｏｒｙ，ａｎｄｉｈｉｌ－ｓｔｅｂａｓｓｏｆｓｔｕｄｉｎｔｈｅｒｏｂｌｅｍｓｓｕｃｈａｓｃ

7、ｏｍｕｔａｔｉｏｎｔｈｅａｏｒｉｔｈｍｄｅｓｃｒｉｙｇｐｐ，ｇｐｔｉｏ打ａｎｄａｎａｌｙｓｉｓａｎｄｃｏｍｕｔａｔｉｏｎａｌｃｏｍｌｅｘｉｔｔｈｅｏｒ．Ｉｎｔｈｅｔｈｅｏｒｏｆａｕｔｏｍａｔａ，，ｐｐｙｙｙ＇ｎａｎｉｍｐｏｉｔａｔｒｅｓｅａｒｃｈｔｏｐｉｃｉｓｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅ打ａｕｔｏｍａｔａａｎｄｒａｍｍａｉＴｓ．ｇＩｎｃｌａｓｓｉｃａｌａｕｔｏｍａｔａｔｈｅｏｒｄｅｔｅｒｍｉｎｉｓｔｉｃｆｉ打化ｅａｕｔｏｍａｔａｎｏｎｄｅｔｅｒｍｉ打ｉｓｔｉｃｆｉｉＵｔｅ

8、ｙ，，ａｕｔｏｍａｔａｒｅｕｌａｒｒａｍｍａｉｒｓｒｅｕｌ