Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "Interchange lemma" – news · newspapers · books · scholar · JSTOR (March 2019) (Learn how and when to remove this message) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (September 2022) (Learn how and when to remove this message) (Learn how and when to remove this message)

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

This grammar-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Formal languages
• Lemmas
• Grammar stubs