On the generative capacity of compound string and array grammars

The operation of composition is a device introduced by Abraham [1] to increase the generative capacity of regular matrix grammars. But not all families of grammars have their generative capacity increased by this operation. P?un [5] has proved that composition increases the generative capacity of linear grammars but not of regular, CF, CS or PS grammars. In this note, we show that the generative power of k-linear (k ? 1) grammars is increased by composition. In fact, it is of interest to note that the families of compound linear and compound k-linear languages are equal. Furthermore, the family of compound linear languages is an AFL, properly contained in the family of CFLs. Certain other families of string and array grammars whose generative capacities are increased by the operation of composition are also provided.