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

Weighted context-free grammars over valuation monoid and their languages

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

Context-free grammars have a strong ability to express languages. In this paper, we introduce the notions of weighted context-free grammars （WCFG） and their weighted context-free languages（WCFL） over valuation monoid. We discuss the weighted Chomsky norm form and weighted Greibach norm form of context-free grammars. It＇s proved that for WCFG over Cauchy product valuation monoid, there is an equivalent Chomsky norm form and Greibach norm form, responding. Furthermore, some properties of context-free grammars and their languages are discussed.