Interchange lemma
In the theory of formal languages, the interchange lemma states a necessary condition for a language to be context-free, just like the pumping lemma for context-free languages.
It states that for every context-free language there is a such that for all for any collection of length words there is a with, and decompositions such that each of,, is independent of, moreover,, and the words are in for every and.
The first application of the interchange lemma was to show that the set of repetitive strings over an alphabet of three or more characters is not context-free.
