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

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

See also

• Pumping lemma for regular languages

References

• William Ogden, Rockford J. Ross, and Karl Winklmann (1982). "An "Interchange Lemma" for Context-Free Languages". SIAM Journal on Computing. 14 (2): 410–415. doi:10.1137/0214031.