zbMATH — the first resource for mathematics

An ”interchange lemma” for context-free languages. (English) Zbl 0601.68051
An ”interchange lemma” is proven, providing a new necessary condition for languages to be context-free. This ”interchange lemma” is then used to show that the set of repetitive strings (i.e. strings of the form xyyz with nonempty y) over an alphabet of three or more characters is not context-free - an issue which in the past has shown remarkable resilience against standard tools for proving languages not context-free and which has only recently been solved independently by A. Ehrenfeucht and G. Rozenberg [RAIRO Inf. Théor. 17, 13-22 (1983; Zbl 0512.68059)] and by R. Ross and K. Winklmann [ibid. 16, 191-199 (1982; Zbl 0489.68071)]. The interchange lemma presented in this paper is a generalization of the proof technique used in the latter paper.

68Q45 Formal languages and automata
Full Text: DOI