Jump to content

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.

See also

[edit]

References

[edit]
  • 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.{{cite journal}}: CS1 maint: multiple names: authors list (link)