  During the last decades, classical models in language theory have been
extended by control mechanisms defined by monoids. We study which monoids cause
the extensions of context-free grammars, finite automata, or finite state
transducers to exceed the capacity of the original model. Furthermore, we
investigate when, in the extended automata model, the nondeterministic variant
differs from the deterministic one in capacity. We show that all these
conditions are in fact equivalent and present an algebraic characterization. In
particular, the open question of whether every language generated by a valence
grammar over a finite monoid is context-free is provided with a positive
answer.
