1
$\begingroup$

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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.