Lema de intercambio

---

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

Se afirma que para cada lenguaje libre de contexto existe un tal que para todo para cualquier colección de longitud de las palabras hay una con , y descomposiciones de tal manera que cada una de , , es independiente de la , por otra parte, y las palabras están en para cada y .${\ Displaystyle L}$${\ Displaystyle c> 0}$${\ Displaystyle n \ geq m \ geq 2}$${\ Displaystyle n}$${\ Displaystyle R \ subconjunto L}$${\ Displaystyle Z = \ {z_ {1}, \ ldots, z_ {k} \} \ subconjunto R}$${\ Displaystyle k \ geq | R | / (cn ^ {2})}$${\ Displaystyle z_ {i} = w_ {i} x_ {i} y_ {i}}$${\ Displaystyle | w_ {i} |}$${\ Displaystyle | x_ {i} |}$${\ Displaystyle | y_ {i} |}$${\ Displaystyle i}$${\ Displaystyle m / 2 <| x_ {i} | \ leq m}$${\ Displaystyle w_ {i} x_ {j} y_ {i}}$${\ Displaystyle L}$${\ Displaystyle i}$${\ Displaystyle j}$

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

---