Lema de intercambio

En la teoría de los lenguajes formales , el lema de intercambio establece una condición necesaria para que un lenguaje sea libre de contexto , al igual que el lema de bombeo para los lenguajes libres de contexto .

Afirma que para cada lenguaje libre de contexto${\displaystyle L}$hay un${\displaystyle c>0}$de tal manera que para todos${\displaystyle n\geq m\geq 2}$para cualquier colección de longitud${\displaystyle n}$palabras${\displaystyle R\subset L}$hay un${\displaystyle Z=\{z_{1},\ldots,z_{k}\}\subset R}$con${\displaystyle k\geq |R|/(cn^{2})}$y descomposiciones${\displaystyle z_{i}=w_{i}x_{i}y_{i}}$de tal manera que cada uno de${\displaystyle |w_{i}|}$,${\displaystyle |x_{i}|}$,${\displaystyle |y_{i}|}$es independiente de${\displaystyle i}$, además,${\displaystyle m/2<|x_{i}|\leq m}$y las palabras${\displaystyle w_{i}x_{j}y_{i}}$están en${\displaystyle L}$por cada${\displaystyle i}$y${\displaystyle j}$.

La primera aplicación del lema de intercambio fue demostrar que el conjunto de cadenas repetitivas (es decir, cadenas de la forma${\displaystyle xyyz}$con${\displaystyle |y|>0}$) sobre un alfabeto de tres o más caracteres no es independiente del contexto.

• Lema de bombeo para lenguajes regulares

• William Ogden, Rockford J. Ross y Karl Winklmann (1982). "Un "lema de intercambio" para lenguajes libres de contexto". SIAM Journal on Computing . 14 (2): 410– 415. doi : 10.1137/0214031 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )