A New–Old Class of Linguistically Motivated Regulated Grammars
Steven I. Marcus, Carlos Martı́n-Vide, Víctor Mitrana, Gh. Păun · 2001
The oldest restriction in the derivation of context-free grammars is believed to be the matrix one, introduced by S. Abraham in 1965. However, in a paper (with solid linguistical motivations) of I. Bellert, published in the same year, there are in nuce the ideas of several control mechanisms considered later, as well as an idea which we do not know to have been explored. In short, conditions about some of the paths from the root to leaf nodes in the derivation trees of a contex-free grammar are considered. We investigate here this type of control, with emphasis on a class which generates a mildly context-sensitive family of languages (in particular, a useful pumping lemma is provided).