FormalLanguage.GrammarProduct.Op

Documentation

gAdd :: Monoid (Add a) => a -> a -> a

gSubtract :: Grammar -> Grammar -> Grammar

gPower :: Grammar -> Integer -> Grammar

(><) :: Grammar -> Grammar -> Grammar

The product of two grammars.

In general, it is quite hard to define the product of two context-free grammars in a way that keeps associativity and also "does what we want it to do" (see paper). For linear grammars it is much easier. Also, for grammars in certain normal forms, a simpler definition is possible. Due to this, we make the choice of the actual way on how to multiply based on the type of grammars given. This, however, should only affect the resulting rules, not the (multi-tape) language that the operations yields.

TODO I think, left-linear could reasonably be expanded to both, left- and right-linear and maybe linear in general.

NOTE A proof for associativity is possible, but generally hard, so we prefer to let the framework perform the proof for us.

(.+) :: Grammar -> Grammar -> Grammar

The addition operation defined for two grammars of the same dimension. It forms a monoid under the Add newtype.