Elimination of λ-Rules From Matrix Grammars with Simple Repeating Structures

We give a partial answer to the problem of elimination of λ-rules from context-free matrix grammars. We utilize the erasing normal form grammar $G'$ of a matrix grammar G, that is, L(G) - \λ\ = L(G') and in $G'$ nonterminals are classified into two types: one derives the empty word λ only, called mortal, and the other never derives λ, called productive. Next we make a mixed symbol which consists of a productive or terminal letter and a number of mortal letters. We prove that every derivation in $G'$ is converted to a derivation in a grammar with the mixed symbols. But the number of mortal letters in mixed symbols, in general, becomes unboundedly large, that is, the ``conversion'' does not make a sound grammar. We show that, if the repeating structures of a sequence of matrices are specific types, then the number of mortals in the mixed symbols is bounded by a constant determined by the grammar. Because the mixed symbols do not have λ-rules, elimination of λ-rules is performed for a specific subclass of matrix grammars.