A Pumping Lemma Scheme for the Control Language Hierarchy

In [9] Weir introduced control grammars as a model for describing the syntactic structure of natural languages. Informally, a control grammar is a pair {G, C} where G is a context-free grammar whose productions are assigned labels from a finite set of labels II, and C (called the control set) is a set of strings over II. A derivation in a control grammar is similar to that in an ordinary context-free grammar except that the control set C is used to further constrain the set of valid derivations. In particular, if one views a derivation as a tree, then (in a manner to be described later) each edge in such a tree is given a label from II according to the production of G associated with the edge. The derivation tree is considered "valid" if certain paths in the tree correspond to strings which are in the control set C. The language generated by the control grammar is then the set of strings having at least one derivation tree in the sense just described.