Several specific models are created by adding counters. For example, indexed grammars are a well-studied general grammatical model like context-free grammars except where nonterminals keep stacks of “indices”. Although this system can generate
non-semilinear languages, linear indexed grammars (indexed grammars with at most one nonterminal in the right hand side of
every production) generate only semilinear languages [1]}. Here, we define linear indexed grammars with counters, akin to linear indexed grammars, where every sentential form contains the usual sentential form, plus \(k\)  counter values; each production operates as usual and can also optionally increase each counter by some amount; and a terminal word can be generated only if it can be produced with all counter values equal. It is shown that the family of languages generated must be semilinear since it is contained in the smallest full AFL containing the intersection of linear indexed languages and \(\)  languages. A characterization is also shown: linear indexed grammars with counters generate exactly those languages obtained by intersecting a linear indexed language with an \(\)  and then applying a homomorphism. Furthermore, it is shown that right linear indexed grammars (where terminals only appear to the left of nonterminals in productions) with counters coincide exactly with the machine model \(\) . Therefore, linear indexed grammars with counters are a natural generalization of \(\)  containing only semilinear languages. This model is generalized once again as follows: an indexed grammar is uncontrolled finite-index if, there is a value \(k\)  such that, for every derivation in the grammar, there are at most \(k\)  occurrences of nonterminals in every sentential form. It is known that every uncontrolled finite-index indexed grammar generates only semilinear languages [2]}, [3]}. It is shown here that uncontrolled finite-index indexed grammars with counters generate only semilinear languages, which is also a natural generalization of both linear indexed grammars with counters and \(\) . This immediately shows decidability of membership, emptiness, and infiniteness for this family.
