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?
