# Interchange lemma

## From Wikipedia, the free encyclopedia

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\geq m\geq 2$ for any collection of length $n$ words $R\subset L$ there is a $Z=\{z_{1},\ldots ,z_{k}\}\subset R$ with $k\geq |R|/(cn^{2})$, and decompositions $z_{i}=w_{i}x_{i}y_{i}$ such that each of $|w_{i}|$, $|x_{i}|$, $|y_{i}|$ is independent of $i$, moreover, $m/2<|x_{i}|\leq m$, and the words $w_{i}x_{j}y_{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.