Let G be a [ CF ] grammar, and let elements of semiring be sets of rules.

Define multiplication as:

$$ x\otimes y = \{ t| \exists r \in x \exists s \in y (t=subst(r,s))\} $$

where $subst(r,s)$ is rewriting of grammar rule $r$ by formal substitution of one symbol in the rule body matching $s$ head with $s$ body. For example, the rule

expr : expr oper expr

matches itself and rewrites into

expr : expr oper expr oper expr

Next, define addition $ \oplus $ as set union.

Is it known semiring?

  • $\begingroup$ add apostrophes before dollar signs to fix that IIRC. $\endgroup$
    – Will Sawin
    Nov 19 '11 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.