An “Interchange Lemma” for Context-Free Languages

Abstract

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 in [5] and [10]. The Interchange Lemma presented in this paper is a generalization of the proof technique used in [10].