检索结果-南通市图书馆

计算机工程与科学 2016年第7期38卷 1405-1412页

作者：赵菲李永明陕西师范大学数学与信息科学学院陕西西安710119

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正... 详细信息

正则文法是研究自动机的重要工具。引入取值于赋值幺半群的加权正则文法、加权类正则文法的定义,讨论了赋值幺半群上加权正则文法、加权类正则文法和加权有限自动机(WFA)的关系。证明了在赋值幺半群上,已知一个加权正则文法或加权类正则文法,分别存在一个WFA与之等价。定义了可分配的赋值幺半群,证明了在可分配的赋值幺半群上已知一个WFA,存在一个加权正则文法和加权类正则文法与之等价,即证明了可分配的赋值幺半群上加权正则文法、加权类正则文法和WFA在生成语言上等价,并举例说明了赋值幺半群的可分配性不是已知WFA存在与之等价的加权正则文法或加权类正则文法的必要条件。

关键词：赋值幺半群加权正则文法加权自动机

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

取值于赋值幺半群的加权下推自动机的代数性质

引用

陕西师范大学学报（自然科学版） 2017年第3期45卷 9-16页

作者：付雯静韩召伟陕西师范大学数学与信息科学学院陕西西安710119

引入取值于赋值幺半群的加权下推自动机、标准型加权下推自动机的定义,证明了在双幺赋值幺半群框架下,加权下推自动机与标准型加权下推自动机相互等价,且以终态方式与以空栈方式识别语言的加权下推自动机能够识别相同的形式幂级数;在Cau... 详细信息

引入取值于赋值幺半群的加权下推自动机、标准型加权下推自动机的定义,证明了在双幺赋值幺半群框架下,加权下推自动机与标准型加权下推自动机相互等价,且以终态方式与以空栈方式识别语言的加权下推自动机能够识别相同的形式幂级数;在Cauchy双幺赋值幺半群上,加权上下文无关语言对于和、连接、正克林闭包运算封闭。结果表明加权下推自动机的诸多性质并不依赖于赋值幺半群的分配律和结合律。

关键词：赋值幺半群双幺赋值幺半群加权下推自动机加权上下文无关语言

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

取值于赋值幺半群的加权上下文无关文法及其语言

引用

模糊系统与数学 2017年第1期31卷 165-173页

作者：王月李永明陕西师范大学数学与信息科学学院陕西西安710119

上下文无关文法是一种表达能力较强的描述语言的方法,在本文中我们引入取值于赋值幺半群的加权上下文无关文法(WCFG)及其产生的加权上下文无关语言(WCFL)。讨论了加权上下文无关文法的加权Chomsky范式文法以及加权Greibach范式文法。证... 详细信息

上下文无关文法是一种表达能力较强的描述语言的方法,在本文中我们引入取值于赋值幺半群的加权上下文无关文法(WCFG)及其产生的加权上下文无关语言(WCFL)。讨论了加权上下文无关文法的加权Chomsky范式文法以及加权Greibach范式文法。证明了对于取值于柯西乘积赋值幺半群上的WCFG,存在与之等价的加权Chomsky范式文法、加权Greibach范式文法;进一步讨论了加权上下文无关文法及其产生的加权上下文无关语言的一些代数性质。

关键词：赋值幺半群加权上下文无关文法加权上下文无关语言加权Chomsky范式加权Greibach范式

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

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

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

引用

作者：赵菲陕西师范大学

学位级别：硕士

自动机理论是计算理论的数学模型,是可计算、算法描述和分析、计算复杂性理论等问题研究的基础.在自动机理论中,一个重要的研究课题是自动机与文法的等价性.在经典自动机理论中,确定型有穷自动机、非确定型有穷自动机与正则文法是等价的... 详细信息

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

关键词：赋值幺半群加权自动机加权正则文法确定型加权自动机确定型加权正则文法

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：