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 there is a such that for all for any collection of length words there is a with , and decompositions such that each of , , is independent of , moreover, , and the words are in for every and .

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