The pumping lemma for well-nested multiple context-free languages

Abstract. Seki et al. (1991) proved a rather weak pumping lemma for multiple context-free languages, which says that any infinite m-multiple context-free language contains a string that is pumpable at some 2m substrings. We prove a pumping lemma of the usual universal form for the subclass consisting of well-nested multiple context-free languages. This is the same class of languages generated by non-duplicating macro grammars and by coupled-context-free grammars.