Interchange lemma for context-free languages

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 $L$ there is a $c>0$ such that for all $n\ge m\ge 2$ for any collection of length $n$ words $R\subset L$ there is a $Z=\{z_1,\dots ,z_k\}\subset R$ with $k\ge |R|/(c{n}^2)$, and decompositions $z_i=w_i{x}_i{y}_i$ such that each of $|w_i|$, $|x_i|$, $|y_i|$ is independent of $i$, moreover, $m/2<|x_i|\le m$, and the words $w_i{x}_j{y}_i$ are in $L$ for every $i$ and $j$.

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

See also

• Pumping lemma for regular languages

External links

• An “Interchange Lemma” for Context-Free Languages

References

• William Ogden, Rockford J. Ross, and Karl Winklmann (1982). "An "Interchange Lemma" for Context-Free Languages". JSIAM J. Comput. 14 (2): 410–415. doi:10.1137/0214031.CS1 maint: Multiple names: authors list (link)

This article "Interchange lemma for context-free languages" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Interchange lemma for context-free languages. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Dynamic syntax tree
• Dot-depth hierarchy
• Union of two regular languages

---