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

来源 :陕西师范大学 | 被引量 : 0次 | 上传用户:missingmm
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
自动机理论是计算理论的数学模型,是可计算、算法描述和分析、计算复杂性理论等问题研究的基础.在自动机理论中,一个重要的研究课题是自动机与文法的等价性.在经典自动机理论中,确定型有穷自动机、非确定型有穷自动机与正则文法是等价的.加权有限自动机(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等价.
其他文献
随着现代客运行业的发展与人们生活水平的不断提升,人们出行的次数越来越多。并且人们出行的时候有时会与他人结伴同行或是一起组团出行,比如与人一起出差、与好朋友一起旅游
采用吸热型碳氢燃料作为冷却剂的再生冷却可以有效地解决超燃冲压发动机的热防护问题。通常用于流量测量的差压式流量计和用于壁面冷却的冷却通道是再生冷却系统的重要组成部
偏微分方程理论可以被应用在许多科学领域,例如生物学,物理学,化学,工程学,控制理论,人口增长模型和气候模型。在过去几年,带有偏差变元的偏微分方程的基础理论的研究得到了
设S是序幺半群.文献[14]中证明了所有强平坦的序左S-系是I-正则的当且仅当S是左PP且左半完全的序幺半群.本文第一部分证明了上述结论中的左半完全性可被更弱的性质(FP2)代替或
研究多维分布时需要考虑其相关性问题,用Copula函数来描述变量间的相关结构,不需要每次计算相同的边缘分布,且任意边缘分布都可以通过Copula函数构造联合分布。因此,许多国内
恢复和保育生态系统服务功能既是人类生存和现代文明的基础,也是实现可持续发展的前提。研究与探讨喀斯特石漠化地区不同土地覆被对生态系统服务功能的影响机制,可为我国西南
图G=(V,E)的边着色是一个映射c:E(G)→S,使得任意两条相邻的边e和f,满足c(e)≠ c(f).图的强边着色是图的边着色并且要求在图中和同一边相邻的两条边也要着不同的颜色.换而言之,在强边
图G的无圈k-边染色是指图G的一个正常边染色且不产生双色圈的k-边染色.图G的无圈边染色数χa’(G)是使得图G有一个无圈k-边染色的最小整数k.在1978年,Fiamcik提出了任意图的
对逻辑代数系统的研究是非经典数理逻辑的一个重要研究方向,为了进一步揭示弱MTL-代数的特性,本文从多个方面对其进行了再研究.首先,讨论了弱MTL-代数的性质,澄清了它与其它
本文研究下面的四阶非线性椭圆边值问题:其中△2是双调和算子,Ω为RN中的具有光滑边界的有界开区域,c∈R.在工程实际中,含有双调和算子的四阶椭圆问题△2u+c△u=f(x,u),z∈ΩQ