Context free derivations on word monoids (Q1263994)

The notion of a (direct) derivation in context free grammars has always been defined on letter monoids generated by total vocabularies of these grammars. This notion is introduced on word monoids generated by finite sets of words over total vocabularies of context free grammars. The resulting grammars are a simple and natural modification of the classic definition of context free grammars. Moreover, their generative capacity is remarkably increased, even when we use very short generators for word monoids. Indeed, using generators of length only at most two, context sensitive and recursively enumerable languages are characterized in a natural way.