Weighted Context-Free Grammars Over Bimonoids

Abstract

We introduce and investigate weighted context-free grammars over an arbitrary bimonoid K. Thus, we do not assume that the operations of K are commutative or idempotent or they distribute over each other. We prove a Chomsky-Schutzenberger type theorem for the series generated by our grammars. Moreover, we show that the class of series generated by weighted right-linear grammars over a linearly ordered alphabet $\Sigma$ and K coincides with that of recognizable series over $\Sigma$ and K.

Keywords

• weights
• context-free grammars
• bimonoids