  State grammars are context-free grammars where the productions have states
associated with them, and a production can only be applied to a nonterminal if
the current state matches the state in the production. Once states are added to
grammars, it is natural to add various stores, similar to machine models. With
such extensions, productions can only be applied if both the state and the
value read from each store matches between the current sentential form and the
production. Here, generative capacity results are presented for different
derivation modes, with and without additional stores. In particular, with the
standard derivation relation, it is shown that adding reversal-bounded counters
does not increase the capacity, and states are enough. Also, state grammars
with reversal-bounded counters that operate using leftmost derivations are
shown to coincide with languages accepted by one-way machines with a pushdown
and reversal-bounded counters, and these are surprisingly shown to be strictly
weaker than state grammars with the standard derivation relation (and no
counters). The complexity of the emptiness problem involving state grammars
with reversal-bounded counters is also studied.
