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 [math]\displaystyle{ L }[/math] there is a [math]\displaystyle{ c\gt 0 }[/math] such that for all [math]\displaystyle{ n\geq m\geq 2 }[/math] for any collection of length [math]\displaystyle{ n }[/math] words [math]\displaystyle{ R\subset L }[/math] there is a [math]\displaystyle{ Z=\{z_1,\ldots,z_k\}\subset R }[/math] with [math]\displaystyle{ k\ge |R|/(cn^2) }[/math], and decompositions [math]\displaystyle{ z_i=w_ix_iy_i }[/math] such that each of [math]\displaystyle{ |w_i| }[/math], [math]\displaystyle{ |x_i| }[/math], [math]\displaystyle{ |y_i| }[/math] is independent of [math]\displaystyle{ i }[/math], moreover, [math]\displaystyle{ m/2\lt |x_i|\leq m }[/math], and the words [math]\displaystyle{ w_ix_jy_i }[/math] are in [math]\displaystyle{ L }[/math] for every [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math].

The first application of the interchange lemma was to show that the set of repetitive strings (i.e., strings of the form [math]\displaystyle{ xyyz }[/math] with [math]\displaystyle{ |y|\gt 0 }[/math]) 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.