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

发布时间：2018-07-04 06:35

  本文选题：赋值幺半群 + 加权上下文无关文法　； 参考：《模糊系统与数学》2017年01期

【摘要】：上下文无关文法是一种表达能力较强的描述语言的方法,在本文中我们引入取值于赋值幺半群的加权上下文无关文法(WCFG)及其产生的加权上下文无关语言(WCFL)。讨论了加权上下文无关文法的加权Chomsky范式文法以及加权Greibach范式文法。证明了对于取值于柯西乘积赋值幺半群上的WCFG,存在与之等价的加权Chomsky范式文法、加权Greibach范式文法;进一步讨论了加权上下文无关文法及其产生的加权上下文无关语言的一些代数性质。
[Abstract]:Context-free grammar is a powerful way to express description language. In this paper, we introduce weighted context-independent grammar (WCFG) and its generated weighted context-independent language (WCFL). The weighted Chomsky normal form grammar and the weighted Greibach normal form grammar are discussed. It is proved that the weighted Chomsky normal form grammars and weighted Greibach normal form grammars are equivalent to WCFG for WCFG which is valued on Cauchy product assignment monoids. Furthermore, some algebraic properties of weighted context-free grammar and its generated weighted context-free language are discussed.
【作者单位】： 陕西师范大学数学与信息科学学院;
【基金】：国家自然科学基金(批准号:11271237,61228305)
【分类号】：O152.7;O159

【相似文献】

相关期刊论文 前6条

1 马世骅;一个万能的ω上下文无关文法[J];科学通报;1986年21期

2 马世骅;万能的ω-上下文无关文法及它的一个应用[J];数学学报;1989年01期

3 盛莉;;格值上下文无关文法的范式[J];纯粹数学与应用数学;2010年02期

4 杨春志;张超;;格值上下文无关文法对基于词的计算[J];重庆交通大学学报(自然科学版);2009年04期

5 谢跃美;田莉萍;万会芳;;最大乘积型Fuzzy上下文无关文法与下推自动机[J];西南交通大学学报;2006年03期

6 ;[J];;年期

相关博士学位论文 前2条

1 郝小健;上下文无关文法，，多元稳定多项式及递增树[D];南开大学;2014年

2 杨瑞龙;几类树结构上统计量的研究[D];南开大学;2014年

本文编号：2095159