simple matrix languages with a leftmost restriction参考-论文.pdf

INFORMATION AND CONTROL 23, 128-139 (1973)
Simple Matrix Languages with a Leftmost Restriction
H. A. MAVRER
University of Karlsruhe, Karlsruhe, Germany
It is shown that every type 1 language can be generated by an e-free simple
matrix grammar (of order 2), if a certain leftmost restriction is imposed on
the application of matrices. Dropping the e-free restriction, every type 0
language can be obtained. This strengthens a result previously established for
matrix grammars.
l. INTRODUCTION
Among the many types of grammars, generating language classes between
the class of context-free and the class of context-sensitive languages are the
(E-free context-free)programmed grammars (Rosenkrantz, 1969), the scattered-
context grammars (Greibach and Hopcroft, 1969), the state grammars (Kasai,
1970), the matrix grammars (Abraham, 1965; Salomaa, 1970; Mayer, 1972)
and the simple matrix grammars (Ibarra 1970; Kuich and Maurer, 1970).
Concerning the generative power of these types of grammars, the (E-free)
state grammars are known to generate all context-sensitive languages (Kasai,
1970), the state grammars allowing e-rules all type 0 languages (Salomaa,
1972); the scattered-context grammars generate only context-sensitive
languages; whether they generate all context-sensitive languages is not known;
the (e-free, context-free) programmed grammars generate some, but not
all context-sensitive languages (Rosenkrantz, 1969); the class of matrix
languages is a subset of the class of (E-free, context-free) programmed
grammars (Salomaa, 1970),whether containment is proper is not known; the
class of simple matrix languages is a proper subset of the class of (E-free,
context-free) programmed languages (Kuich and Maurer, 1970).
That the generative power of grammars can sometimes be increased by
imposing "leftmost" restrictions on the