Prueba del lema de bombeo para lenguajes sin contexto utilizando autómatas pushdown

El lema de bombeo para los idiomas regulares se puede probar considerando un autómata de estado finito que reconoce el idioma estudiado, escogiendo una cadena con una longitud mayor que su número de estados y aplicando el principio del casillero. El lema de bombeo para lenguajes libres de contexto (así como el lema de Ogden, que es ligeramente más general), sin embargo, se prueba por considerar una gramática independiente del contexto de la lengua estudiada, recogiendo una cadena suficientemente larga, y mirando el árbol de análisis sintáctico.

Dada la similitud de los dos lemas de bombeo, es de esperar que el contexto libre también se pueda probar de manera similar al normal considerando un autómata pushdown que reconoce el idioma, en lugar de una gramática. Sin embargo, no pude encontrar ninguna referencia a tal prueba.

De ahí mi pregunta: ¿hay una prueba del lema de bombeo para lenguajes libres de contexto que solo involucra autómatas pushdown y no gramáticas?

Pensé en este problema nuevamente, y creo que tengo una prueba completa. Es un poco más complicado de lo que esperaba. ¡Los comentarios son bienvenidos! Actualización: envié esta prueba en arXiv, en caso de que esto sea útil para alguien: http://arxiv.org/abs/1207.2819

$\DeclareMathOperator{\fp}{fp}$ $\DeclareMathOperator{\lp}{lp}$ $\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$ $\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$

Deje que sea ​​un lenguaje sin contexto sobre un alfabeto . Deje ser un autómata pushdown que reconoce , con alfabeto de pila . Denotamos porel número de estados de . Sin pérdida de generalidad, podemos suponer que las transiciones de resaltan el símbolo superior de la pila y no presionan ningún símbolo en la pila o presionan en la pila el símbolo superior anterior y algún otro símbolo.Σ A L Γ | A | A $L$$\Sigma$$A$$L$$\Gamma$$|A|$$A$$A$

Definimosy la longitud de bombeo, y mostrará que todo tal que tiene una descomposición de la forma tal que , y .p = | A | ( | Γ | + 1 ) p ′ w ∈ L | w | > p w = u v x y z | v x y | ≤ p | v y | ≥ 1 ∀ n ≥ 0 , u v n$p' = |A|^2 |\Gamma|$$p = |A| (|\Gamma|+1)^{p'}$$w \in L$$|w| > p$$w = u v x y z$$|vxy| \leq p$$|vy| \geq 1$$\forall n \geq 0, u v^n x y^n z \in L$

Deje tal que . Sea una ruta de aceptación de longitud mínima para (representada como una secuencia de transiciones de ), denotamos su longitud por. Podemos definir, para, el tamaño de la pila en la posición de la ruta de aceptación. Para todos , definimos un nivel sobre como un conjunto de tres índices con tal que:| w | > p π w A | π | 0 ≤ i < | π | s i i N > 0 N π i , j , k 0 ≤ i < j < k ≤ $w \in L$$|w| > p$$\pi$$w$$A$$|\pi|$$0 \leq i < |\pi|$$s_i$$i$$N > 0$$N$$\pi$$i, j, k$$0 \leq i < j < k \leq p$

1. $s_i = s_k, s_j = s_i + N$
2. para todo tal que ,i ≤ n ≤ j s i ≤ s n ≤ s $n$$i \leq n \leq j$$s_i \leq s_n \leq s_j$
3. para todo tal que , .j ≤ n ≤ k s k ≤ s n ≤ s $n$$j \leq n \leq k$$s_k \leq s_n \leq s_k$

(Para ver un ejemplo de esto, vea la imagen para el caso 2 a continuación que ilustra un nivel).$N$

Definimos el nivel de como el máximo, de modo que tiene un nivelEsta definición está motivada por la siguiente propiedad: si el tamaño de la pila sobre una ruta es mayor que su nivel , entonces los símbolos de la pila de más de niveles de profundidad nunca aparecerán. Ahora distinguiremos dos casos: , en cuyo caso sabemos que la misma configuración para el estado del autómata y los símbolos superiores de la pila se encuentran dos veces en los primeros pasos de , oπ N π N π l l l < p ′ l p + 1 π l ≥ p ′ v $l$$\pi$$N$$\pi$$N$$\pi$$l$$l$$l < p'$$l$$p+1$$\pi$$l \geq p'$, y debe haber una posición de apilamiento y desapilamiento que pueda repetirse un número arbitrario de veces, a partir de la cual construimos e .$v$$y$

Caso 1. . Definimos las configuraciones de ya que las parejas de un estado de y una secuencia de símbolos de pila (donde pilas de tamaño inferior a a ser representado por un relleno a con un símbolo blanco especial, que es por eso que usamos al definir ). Por definición, hay tales configuraciones, que es menor que . Por lo tanto, en los primeros pasos de de , la misma configuración se encuentra dos veces en dos posiciones diferentes, digamos . Denotamos por A A $l < p'$$A$$A$$l$l | Γ | + 1 p | A | ( | Gamma | + 1 ) l p p + 1 π i < j i j w i j π i ≤ j w = u v x y z y z = ε u = w 0 ⋯ i v = $l$$l$$|\Gamma| + 1$$p$$|A| (|\Gamma| + 1)^l$$p$$p+1$$\pi$$i < j$$\widehat{i}$ (resp. ) la posición de la última letra de leída en el paso (resp. ) de . Tenemos . Por lo tanto, podemos factorizar con , , , . (Por denotamos las letras de de inclusivo a exclusivo.) Por construcción, .$\widehat{j}$$w$$i$$j$$\pi$$\widehat{i} \leq \widehat{j}$$w = u v x y z$$y z = \epsilon$$u = w_{0 \cdots \widehat{i}}$ x=w j ⋯| w| wx⋯ywxy| vxy| ≤$v = w_{\widehat{i} \cdots \widehat{j}}$$x = w_{\widehat{j} \cdots |w|}$$w_{x \cdots y}$$w$$x$$y$$|vxy| \leq p$

También tenemos que mostrar que , pero esto se deduce de nuestra observación anterior: los símbolos de pila más profundos que nunca aparecen, por lo que no hay forma de distinguir configuraciones que son iguales de acuerdo con nuestra definición, y una ruta de aceptación para se construye a partir de la de repitiendo los pasos entre y , veces.l u v n x w i j $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$$l$$u v^n x$$w$$i$$j$$n$

Finalmente, también tenemos , porque si , entonces, porque tenemos la misma configuración en los pasos y en , sería un camino de aceptación para , contradiciendo la minimidad de .v = ϵ i j π π ′ = π 0 ⋯ i π j ⋯ | π | w $|v| > 0$$v = \epsilon$$i$$j$$\pi$$\pi' = \pi_{0 \cdots i} \pi_{j \cdots |\pi|}$$w$$\pi$

(Tenga en cuenta que este caso equivale a aplicar el lema de bombeo para idiomas regulares codificando los símbolos de la pila superiores en el estado del autómata, lo cual es adecuado porque es lo suficientemente pequeño como para garantizar que sea ​​mayor que el número de estados de este autómata El truco principal es que debemos ajustar para -transitions.)l | w | $l$$l$$|w|$$\epsilon$

Caso 2. . Sea un nivel . Para cualquier tamaño de pila , , asociamos el último push y el primer pop . Por definición, y . Aquí hay una ilustración de esta construcción. Para simplificar el dibujo, omito la distinción entre las posiciones de ruta y las posiciones de palabras que tendremos que hacer más adelante.$l \geq p'$$i, j, k$$p'$$h$$s_i \leq h \leq s_j$ fp ( h ) = min ( { y ≥ j | s y = h } ) i ≤ lp ( $\lp(h) = \max(\{y \leq j | s_y = h\})$ $\fp(h) = \min(\{y \geq j | s_y = h\})$j ≤ fp ( h ) ≤ $i \leq \lp(h) \leq j$$j \leq \fp(h) \leq k$

Decimos que el estado completo de un tamaño de pila es el triple formado por:$h$

1. El estado del autómata en la posición$\lp(h)$
2. el símbolo de la pila superior en la posición$\lp(h)$
3. El estado del autómata en la posición$\fp(h)$

Hay posibles estados completos, y tamaños pila entre y así, por el principio del palomar, existen, dos pila tamaños con de tal manera que los estados completos en y son la misma. Como en el caso 1, definimos por , , y las posiciones de las últimas letras de leídas en las posiciones correspondientes en . Nos factor de dondep ′ + 1 s i s j g , h s i ≤ g < h ≤ s j g h ^ lp ( g ) ^ lp ( h ) ^ fp ( h ) ^ fp ( g ) w π w = u v x y z u = w 0 ⋯ ^ lp $p'$$p' + 1$$s_i$$s_j$$g, h$$s_i \leq g < h \leq s_j$$g$$h$$\lpp(g)$$\lpp(h)$$\fpp(h)$$\fpp(g)$$w$$\pi$$w = u v x y z$ v= w ^ lp ( g ) ⋯ ^ lp ( h ) x= w ^ lp ( h ) ⋯ ^ fp ( h ) y= w ^ fp ( h ) ⋯ ^ fp ( g ) z= w ^ fp ( g ) ⋯ | w $u = w_{0 \cdots \lpp(g)}$, , , , y .$v = w_{\lpp(g) \cdots \lpp(h)}$$x = w_{\lpp(h) \cdots \fpp(h)}$$y = w_{\fpp(h) \cdots \fpp(g)}$$z = w_{\fpp(g) \cdots |w|}$

Esta factorización asegura que (porque según nuestra definición de niveles).k ≤ $|vxy| \leq p$$k \leq p$

También tenemos que demostrar que . Para hacerlo, observe que cada vez que repetimos , comenzamos desde el mismo estado y la misma pila superior y no saltamos por debajo de nuestra posición actual en la pila (de lo contrario, tendríamos que presionar nuevamente en la posición actual, violando la maximidad de ), por lo que podemos seguir la misma ruta en y presionar la misma secuencia de símbolos en la pila. Por la maximidad de y la minimidad de , mientras leemos , no saltamos por debajo de nuestra posición actual en la pila, por lo que la ruta seguida en el autómata es la misma independientemente del número de veces repetimosv lp ( g ) A lp ( h ) fp ( h ) x v w v v v fp ( g ) A u v n x y n z $\forall n \geq 0, u v^n x y^n z \in L$$v$$\lp(g)$$A$$\lp(h)$$\fp(h)$$x$$v$. Ahora, si repetimos tantas veces como repetimos , ya que comenzamos desde el mismo estado, ya que hemos empujado la misma secuencia de símbolos en la pila con nuestras repeticiones de , y dado que no mostramos más de lo que tiene apilados por la minimidad de , podemos seguir la misma ruta en y extraer la misma secuencia de símbolos de la pila. Por lo tanto, se puede construir una ruta de aceptación desde partir de la ruta de aceptación para .$w$$v$$v$$v$$\fp(g)$$A$$u v^n x y^n z$$w$

Finalmente, también tenemos , porque como en el caso 1, si e , podemos construir una ruta de aceptación más corta para eliminando y .v = ϵ y = ϵ w π lp ( g ) ⋯ lp ( h ) π fp ( h ) ⋯ fp ( g $|vy| > 1$$v = \epsilon$$y = \epsilon$$w$$\pi_{\lp(g)\cdots\lp(h)}$$\pi_{\fp(h)\cdots\fp(g)}$

Por lo tanto, tenemos una factorización adecuada en ambos casos, y el resultado está probado.

(El crédito es para Marc Jeanmougin por ayudarme con esta prueba).

Sí, es posible. Podríamos usar la noción de configuraciones de superficie; fueron presentados por Cook hace mucho tiempo. Con esto, debería ser bastante fácil obtener una versión de lemma de bombeo.

En cuanto a las configuraciones de superficie, casi cualquier documento sobre LogCFL debería llevar su definición. Aquí hay un artículo reciente y una tesis.

¡Quizás alguien más enérgico pueda explicar los detalles!

Para completar, una referencia a una prueba en esta dirección.

A.Ehrenfeucht, HJHoogeboom, G.Rozenberg: Sistemas de pares coordinados. I: palabras Dyck y bombeo clásico RAIRO, Inf. Théor. Appl. 20, 405-424 (1986)

Resumen. La noción de un sistema de pares coordinados [...] corresponde muy estrechamente a (es otra formulación de) la noción de un autómata push-down. En este artículo [...] investigamos la posibilidad de obtener propiedades de bombeo de lenguajes libres de contexto a través del análisis de cálculos en sistemas cp. Para hacer esto, analizamos la estructura combinatoria de las palabras de Dyck. Las propiedades de las palabras de Dyck que investigamos provienen del análisis combinatorio de cálculos en sistemas cp. Demostramos cómo se puede utilizar esta correspondencia para probar el lema de bombeo clásico.

Al discutir este problema con Géraud Sénizergues, me señaló este artículo de Sakarovitch que ya prueba este resultado. La prueba parece remontarse a este artículo de Ogden.

Referencias

• Sakarovitch, Jacques. Sur une propriété d'itération des langages algébriques déterministes. (Francés. Resumen en inglés). Mates. Teoría de sistemas 14 (1981), no. 3, 247–288.
• William F. Ogden. 1969. Teoremas de intercalación para lenguajes de pila. En Actas del primer simposio anual de ACM sobre Teoría de la computación (STOC '69).