ON EQUAL MATRIX LANGUAGES

A generative grammar called equal matrix grammar which generates a class which meets both context-sensitive and context-free languages is defined and the formal power series generated by context-free grammars is extended to grammars of this system. The Parikh mapping of this family of languages is shown to be semilinear. The Boolean and closure properties of a certain subfamily are examined. For this subfamily, the generative power of equal matrix grammar is higher than that of context-free grammars. For certain inherently ambiguous context-free languages, including that of Parikh, unambiguous grammars of this class exist. The application of equal matrix grammar to the generation of Tamil kernel sentences is given in the appendix. © 1969 Academic Press, Inc.