1 Answers
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 L {\displaystyle L} there is a c > 0 {\displaystyle c>0} such that for all n ≥ m ≥ 2 {\displaystyle n\geq m\geq 2} for any collection of length n {\displaystyle n} words R ⊂ L {\displaystyle R\subset L} there is a Z = { z 1 , … , z k } ⊂ R {\displaystyle Z=\{z_{1},\ldots ,z_{k}\}\subset R} with k ≥ | R | / {\displaystyle k\geq |R|/} , and decompositions z i = w i x i y i {\displaystyle z_{i}=w_{i}x_{i}y_{i}} such that each of | w i | {\displaystyle |w_{i}|} , | x i | {\displaystyle |x_{i}|} , | y i | {\displaystyle |y_{i}|} is independent of i {\displaystyle i} , moreover, m / 2 < | x i | ≤ m {\displaystyle m/2<|x_{i}|\leq m} , and the words w i x j y i {\displaystyle w_{i}x_{j}y_{i}} are in L {\displaystyle L} for every i {\displaystyle i} and j {\displaystyle j}.
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.