¿Ejemplo de un lenguaje sin contexto que, sin embargo, PUEDE ser bombeado?

Entonces, básicamente, L satisface las condiciones del lema de bombeo para los CFL pero no es un CFL (eso es posible de acuerdo con la definición del lema).

El ejemplo clásico es . Wise muestra en su artículo Un fuerte lema de bombeo para lenguajes libres de contexto que ni el lema de bombeo de Bar-Hillel ni el teorema de Parikh (que indica que el conjunto de longitudes de palabras en un lenguaje libre de contexto es semi-lineal) puede probarse que L no está libre de contexto. Otros trucos como la intersección con un lenguaje regular tampoco ayudan. (El lema de Ogden, una generalización del lema de bombeo de Bar-Hillel, prueba que $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$$L$$L$no está libre de contexto.) También proporciona un lema de bombeo alternativo que es equivalente a la libertad de contexto (para lenguajes computables), y lo usa para demostrar que no está libre de contexto.$L$

El lema de Wise dice que un lenguaje está libre de contexto si y solo si hay una gramática (sin restricciones) G que genera L y un entero k tal que siempre que G genere una "forma oracional" s (por lo que s puede incluir no terminales) de longitud | s | > k , podemos escribir s = u v x y z donde x , v y no están vacías, | v x y | ≤ $L$$G$$L$$k$$G$$s$$s$$|s| > k$$s = uvxyz$$x,vy$$|vxy| \leq k$, Y hay un no terminal de tal manera que G genera u A z y A genera tanto v A y y $A$$G$$uAz$$A$$vAy$$x$ .

Al aplicar repetidamente la condición en el lema, Wise puede demostrar que no está libre de contexto, pero los detalles son algo complicados. También da una condición equivalente aún más complicada, y la usa para demostrar que el lenguaje { a n b a n m : n , m > 0 $L$$\{ a^n b a^{nm} : n,m > 0 \}$ no puede escribirse como una intersección finita de lenguajes libres de contexto.

Si no puede acceder al documento de Wise (está detrás de un muro de pago), hay una versión mecanografiada que salió como un informe técnico de la universidad de Indiana.

---

Johnsonbaugh y Miller, Converse de bombear lemas , atribuyen un lenguaje sin contexto que satisface la condición de bombeo del lema de Ogden , y lo atribuyen allí a Boasson y Horvath, sobre idiomas que satisfacen el lema de Ogden . El idioma en cuestión es Podemos escribirL′=L1∪

$$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$$ $L' = L_1 \cup L_2$ , correspondiente a las dos líneas diferentes. Tenga en cuenta que y que L 2 es regular. El lema de Ogden se puede usar para demostrar que L 1 no está libre de contexto, y tampoco lo está L ' , pero no se puede usardirectamentepara mostrar que L ' no está libre de contexto.$L_1 \cap L_2 = \emptyset$$L_2$$L_1$$L'$$L'$

Aún más simple: . Siempre puede bombear el a s; La intersección con la L regular ( a b + c + d + ) da una no CFL (y eso se puede probar bombeando lemma).$\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$$a$$\mathcal{L}(a b^+ c^+ d^+)$

A simple language is $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$. Intersect with $\mathcal{L}(a b^+ c^+ d^+)$ to get a clearly non-CFL, but you can always pump the $a$, and mimetize the equal-length-ness in the sea of ${}^+$.