Interchange lemma

{{Multiple issues|

{{primary sources|date=March 2019}}

{{No footnotes|date=September 2022}}

}}

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$ there is a $c>0$ such that for all $n\backslash geq\; m\backslash geq\; 2$ for any collection of length $n$ words $R\backslash subset\; L$ there is a $Z=\backslash \{z\_1,\backslash ldots,z\_k\backslash \}\backslash subset\; R$ with $k\backslash ge\; |R|/(cn^2)$, and decompositions $z\_i=w\_ix\_iy\_i$ such that each of $|w\_i|$, $|x\_i|$, $|y\_i|$ is independent of $i$, moreover, , and the words $w\_ix\_jy\_i$ are in $L$ for every $i$ and $j$.

The first application of the interchange lemma was to show that the set of repetitive strings (i.e., strings of the form $xyyz$ with $|y|>0$) over an alphabet of three or more characters is not context-free.