Teoría de Lenguajes Clase Teórica 8 Propiedades de Lenguajes Independientes de Contexto y su Lema de “Pumping” Primer cuartimestre 2014 Estas notas están basadas en el material compilado por el Profesor Julio Jacobo a lo largo de distintas ediciones de la materia Teoría de Lenguajes en el Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires. Bibliografía: Capítulo 6 y 7, Introduction to Automata Theory, Languages and Computation, J. Hopcroft, R. Motwani, J. Ullman, Second Edition, Addison Wesley, 2001. Definición (Árbol de derivación). Sea G “ xVN , VT , P, Sy una gramática independiente de contexto, y sea α P VT˚ . Un árbol de derivación para α en G es tal que 1. cada vértice posee una etiqueta que pertenece al conjunto VN Y VT Y tλu. 2. la etiqueta de la raiz es el símbolo distinguido 3. si un vértice es interior, su etiqueta debe pertenecer a VN . 4. si un vértice n posee la etiqueta A y sus hijos n1 , . . . , nk poseen etiquetas X1 , . . . , Xk respectivamente, entonces A Ñ X1 , . . . , Xk debe ser una producción de P . 5. si un vértice posee la etiqueta λ, entonces es una hoja y es el único hijo de su padre. Ejemplo. Dada la gramática G “ xtEu , t`, ˚, id, constu , P, Ey con P “t E E E E

Ñ E ` E, Ñ E ˚ E, Ñ id, Ñ constu,

Un Árbol de derivación posible de la cadena id + id * id es

1

Definición. Derivación más a la izquierda ñ es aquella derivación en la que L

α1 Aα2 ñ α1 α1 α2 si A Ñ α1 P P y α1 P VT˚ . L

Definición. Derivación más a la derecha ñ es aquella derivación en la que R

α1 Aα2 ñ α1 α1 α2 si A Ñ α1 P P y α2 P VT˚ . R

Definición (Gramáticas ambiguas). Una gramática independiente del contexto G es ambigua si Dα P L pGq tal que ésta posee más de un árbol de derivación más a la izquierda. Ejemplo. Siguiendo con la gramática del ejemplo anterior, podemos encontrar este otro árbol de derivación más a la izqueirda para la cadena id + id * id

Ejemplo. Ejemplo de gramática no ambigua (distinta de la anterior porque agrega paréntesis) E ÑE`T |T T ÑT ˚F |F F Ñ id | const | pEq

2

Muchos lenguajes admiten tanto gramáticas ambiguas como no ambiguas. Los leguajes determinísticos independientes del contexto son no ambiguos. Y hay una clase importante de lenguajes no ambiguos no determinísticos independientes del contexto. Definición. Un lenguaje independiente de contexto L es intrínsecamente ambiguo si solamente admite gramáticas ambiguas. Un ejemplo de un lenguaje inherentemente ambiguo es tan bm cm dn |n, m ą 0u Y tan bn cm dm |n, m ą 0u. Este conjunto es independiente del contexto porque es la unión de dos conjuntos que lo son (ver Teorema 3). Hopcroft y Ullman (1979) demostraron que no hay forma de derivar de manera no ambigua las cadenas del subconjunto (que no es independiente del contexto) tan bn cn dn |n ą 0u, que es la intersección de ambos lengiuajes. El problema de la decisión de si una gramática es ambigua o no, es indecidible. Es equivalente al problema de correspondencia de Post. Definición. Sea X P VT o X P VN . Llamamos camino de X en un árbol T pAq, a la cadena A, X1 , . . . , Xk , X tal que A ñ . . . X1 . . . ñ . . . X2 . . . ñ . . . . . . ñ . . . Xk . . . ñ . . . X . . .. Definición. La altura de T pAq es m´ ax t|α| : αx es un camino de x y x es una hoja de T pAqu Lema 1. Sea G “ xVN , VT , P, Sy una gramática independiente de contexto con P ‰ H, sea α P pVN Y VT q˚ y sea T pSq un árbol de derivación para α en G cuya altura designaremos h. Sea a “ m´ ax tk : pk “ |β|, A Ñ β P P, β ­“ λq o pk “ 1, A Ñ λ P P qu . Entonces ah ě |α|. Demostración. Por inducción en h. Caso base, h “ 0. El único árbol de derivación posible es el símbolo distinguido S, cuya altura es 0. Por lo tanto 1 “ |S| ď ah “ a0 “ 1. Caso inductivo, h ě 1. Sea γ la base del árbol T pSq para la altura h. Asumamos HI: |γ| ď ah . Sea α la base de T pSq para la altura h ` 1.

Luego |α| ď a |γ|. Pero, por H.I. |γ| ď ah , entonces |α| ď a |γ| ď aah “ ah`1 . 3

Lema 2 (“ Pumping” para lenguajes independientes del contexto.). Para todo lenguaje L independiente del contexto, existe n ą 0 tal que para toda cadena α P L tal que |α ě n|, Dr, x, y, z, s,

α “ rxyzs @i ě 0,

^ |xyz| ď n i

^ |xz| ě 1

^

i

prx yz s P Lq.

Demostración. Sea G una gramática libre del contexto tal que L “ L pGq y sea a “ m´ ax tk : pk “ |β|, A Ñ β P P, β ­“ λq o pk “ 1, A Ñ λ P P qu . |VN |`1

Tomemos n “ a y consideremos una cadena α P L tal que |α| ě n. Sea T pSq un árbol de derivación para α, de altura mínima. Por el Lema 1, ah ě |α|, por lo que ah ě |α| ě n “ a|VN |`1 . Entonces, h ě |VN | ` 1.

Hay un camino au terminales de α de longitud mayor o igual a |VN | ` 1. Como la cantidad de símbolos no terminales es |VN |, entonces en ese camino existe un no-terminal repetido. Llamémoslo A. Recorriendo dicho camino en forma ascendente consideremos la primera y la segunda aparición de A, tal como se ve en la figura. La segunda aparición de A da lugar a la cadena xyz. La altura del árbol generado por esta segunda aparición T pAq es menor o igual que |VN | ` 1, por lo tanto, |xyz| ď a|VN |`1 “ n Notar que x y z no puedn ser simultáneamente nulas, ya que sino el árbol de derivación de α no sería de altura mínima. Luego, existen cadenas r, x, y, zs P VT˚ tal que α “ rxyzn, |xyz| ď n, |xz| ě 1, y ˚

˚

˚

S ñ rAs ñ rxAzs ñ rxyzs. ˚

˚

Entonces, A ñ y pero también A ñ xAz. Demostremos que @i ě 0, rxi yz i s P L, por inducción en i. ˚ ˚ Caso Base, i “ 0. Tenemos que S ñ rAs ñ rys. Por lo tanto, rx0 yz 0 s “ rys P L. i Caso inductivo., i ě 0. Asumamos HI: rx yz i s P L. Veamos que se cumple para i ` 1. Sabemos que ˚

˚

S ñ rxi Az i s ñ rxi yz i s. Pero entonces también se cumple que ˚

˚

˚

S ñ rxi Az i s ñ rxi xAzz i s ñ rxi xyzz i s “ rxi`1 yz i`1 s. Por lo tanto rxi`1 yz i`1 s P L. 4

Ejemplo. El lenguaje L “ tam bm cm : m ě 1u no es independiente del contexto. Demostración: Asumamos que L es independiente del contexto. Sea n dado por el Lema de Pumping, y sea α “ an bn cn . La longitud n no puede incluir al mismo tiempo aes y cs.Por el Lema de Pumping, (1) aes and bs están repetidas, y c permanecen igual, o bien (2) bs y cs se repiten y las aes permanecen igual. Esto contradice que L es independiente del contexto. Ejemplo. El lenguaje L “ tww : w P ta, bu˚ u no es independiente del contexto. Demostración: Asumamos que sí. Sea n dado por el Lema de Pumping, y sea α “ an bn an bn . La longitud n no puede incluir las aes en la primera mitad y las aes en la segunda mitad, Lo mismo ocurre para las bs. Luego, por le Lema de Pumping, a y b pueden repetirse en una mitad, pero no en la otra. Esto contradice que L es independiente del contexto. 2

Ejemplo. El lenguaje L “ tam : m ě 0u no es independiente del contexto. Demostración: Asumamos que sí. Sean 2 n dado por el Lema de Pumping. Sea α “ an . La cadena de longitud inmediatamente mayor que la de α en L tiene longitud pn ` 1q2 . Por el Lema de Pumping la cantidad de aes que puede ser repetidas es menor o igual que n. Pero esto no alcanza para llegar a la longitud pn ` 1q2 de aes, ya que n2 ` n ă pn ` 1q2 Esto contradice que L es independiente del contexto. Teorema 3. Si L1 y L2 son dos lenguajes independientes del contexto, entonces L1 Y L2 lo es también. Demostración. Como L1 y L2 son dos lenguajes independientes del contexto, entonces existen dos gramáticas independientes del contexto G1 “ xVN1 , Σ, P1 , S1 y y G2 “ xVN2 , Σ, P2 , S2 y tales que L1 “ L pG1 q y L2 “ L pG2 q. Supongamos además, sin pérdida de generalidad que VN1 X VN2 “ H. Definamos entonces G “ xVN1 Y VN2 Y tSu , Σ, P1 Y P2 Y tS Ñ S1 , S Ñ S2 u , Sy . Puede demostrarse que @α P Σ˚ , α P L pGq ô α P L pG1 q Y L pG2 q. Teorema 4. Si L1 y L2 son dos lenguajes independientes del contexto, entonces L1 L2 lo es también. Demostración. Como L1 y L2 son dos lenguajes independientes del contexto, entonces existen dos gramáticas independientes del contexto G1 “ xVN1 , Σ, P1 , S1 y y G2 “ xVN2 , Σ, P2 , S2 y tales que L1 “ L pG1 q y L2 “ L pG2 q. Supongamos además, sin pérdida de generalidad que VN1 X VN2 “ H. Definamos entonces G “ xVN1 Y VN2 Y tSu , Σ, P1 Y P2 Y tS Ñ S1 S2 u , Sy . Puede demostrarse que @α P Σ˚ , α P L pGq ô α P L pG1 q L pG2 q. Teorema 5. Si L1 es un lenguaje independiente del contexto, entonces L` 1 lo es también. Demostración. Como L1 es un lenguaje independiente del contexto, entonces existe una gramática independiente del contexto G1 “ xVN1 , Σ, P1 , S1 y tal que L1 “ L pG1 q. Definamos entonces G “ xVN1 Y tSu , Σ, P1 Y tS Ñ S1 S, S Ñ S1 u , Sy . `

Puede demostrarse que @α P Σ˚ , α P L pGq ô α P L pG1 q . Teorema 6. Si L1 y L2 son dos lenguajes independientes del contexto, entonces L1 X L2 no siempre es un lenguaje independiente del contexto. Demostración. Sean L1 “ an bm cl : m, n, l ě 0

^

L2 “ an bm cl : n, m, l ě 0

^

( n“m ( m“l .

Son lenguajes independientes del contexto ya que, L1 “ LpG1 q donde G1 “ xtS, A, Cu , ta, b, cu , tS Ñ AC | C, A Ñ aAb | ab, C Ñ cC | λu , Sy Lo mismo puede hacerse para L2 . Pero L1 X L2 “ tam bm cm : m ě 0u , no es independiente del contexto (ver ejemplo de arriba). 5

Corolario 7. Los lenguajes independientes del contexto están cerrados por unión, concatenación y clausura de Kleene. No están cerrados por intersección, diferencia, complemento. Definición (Lenguaje independiente de contexto determinístico). Un lenguaje L es independiente de contexto determinístico si existe un autómata de pila determinístico (APD) M tal que L “ LpM q. Teorema 8. El complemento de un lenguaje independiente de contexto determinìstico es otro lenguaje independiente de contexto determinìstico. Idea ingenua para la demostración, que no funciona. Dar un autómata de pila qu reconozca el lenguaje, y definir otro donde los estados finales pasen a ser no-finales y viceversa. No funciona porque: Puede ocurrir que el autómata no consuma totalmente todas las cadenas de entrada. Esto puede deberse a 1. el autómata alcanza una configuración desde la cual ninguna transición es posible 2. el autómata entra en un ciclo infinito de transiciones λ En ambos casos, la cadena no consumida es rechazada en ambos autómatas (con y sin intercambiar estados finales con no-finales). Por lo tanto, el lenguaje aceptado por el nuevo autómata no es el complemento del lenguaje aceptado por el autómata original. Puede ocurrir que el autómata consuma todas las cadenas de entrada, pero que exista alguna cadena que, luego de consumida, deje al autómata en una configuración tal que éste pueda hacer transiciones λ pasando por estados finales y no-finales. Por lo tanto, el lenguaje aceptado por el nuevo autómata no es el complemento del lenguaje aceptado por el autómata original. Lema 9. Para todo APD M , existe otro otro APD M 1 equivalente que siempre consume la cadena de entrada. Demostración. Dado el APD M “ xQ, Σ, Γ, δ, q0 , Z0 , F y, definimos @ ( D M 1 “ Q Y q01 , d, f , Σ, Γ Y tX0 u , δ 1 , q01 , X0 , F Y tf u donde 1. δ 1 pq01 , λ, X0 q “ pq0 , Z0 X0 q para evitar que el APD se detenga por haberse vaciado la pila. 2. @q P Q, a P Σ, Z P Γ, si δ pq, a, Zq “ δ pq, λ, Zq “ φ entonces δ 1 pq, a, Zq “ pd, Zq y @q P Q, a P Σ, δ 1 pq, a, X0 q “ pd, X0 q 3. @a P Σ, Z P Γ Y tX0 u , δ 1 pd, a, Zq “ pd, Zq para setear el estado trampa. 4. si para q P Q, Z P Γ, ocurre que i

@i ě 1, Dqi , γi para los cuales pq, λ, Zq $ pqi , λ, γi q (loop λ) entonces, si ningún qi es final δ 1 pq, λ, Zq “ pd, Zq , sino δ 1 pq, λ, Zq “ pf, Zq . 5. para todo Z P Γ Y tX0 u δ 1 pf, λ, Zq “ pd, Zq 6. para todo q P Q, a P Σ Y tλu , Z P Γ, si δ 1 pq, a, Zq no ha sido definida por 2 o 4 entonces δ 1 pq, a, Zq “ δ pq, a, Zq 6

El APD M 1 así definido consume siempre toda la cadena de entrada. Para verlo consideremos lo siguiente: supongamos que existe una cadena de entrada xy tal que M 1 no consume más allá del prefijo x, entonces debe ocurrir que `

˘ ˚ q01 , xy, X0 $ pq, y, Z1 , . . . Zk X0 q M

y que a partir de esa configuración instantánea, no se consume más entrada. Pero esto no puede ocurrir ni porque no existen transiciones posibles (por la regla 2), ni porque se entró en un ciclo infinito de trancisiones λ (por la regla 4). Demostración del Teorema 8. Dado el APD M “ xQ, Σ, Γ, δ, q0 , Z0 , F y, que por lo ya visto podemos considerar que consume toda la cadena de entrada, definimos M 1 “ xQ1 , Σ, Γ, δ 1 , q01 , Z0 , F 1 y un APD donde Q1 “ trq, ks : q P Q y k “ 1, 2 ó 3u , F 1 “ trq, 3s : q P Qu y " q01 “

rq0 , 1s si q0 P F rq0 , 2s si q0 R F

El propósito de k es detectar si entre transiciones con consumo de entrada se ha pasado o no por un estado final. Si se ha pasado por un estado final, entonces se hará k “ 1, sino se hará k “ 2.

7

La función de transición δ 1 se define por 1. Si δ pq, λ, Zq “ pp, γq entonces, para k “ 1, 2 " 1

δ prq, ks , λ, Zq “

prp, 1s , γq si k “ 1 ó p P F prp, 2s , γq si no

2. Si δ pq, a, Zq “ pp, γq entonces, para k “ 1, 2 δ 1 prq, 2s , λ, Zq “ prq, 3s , Zq y " 1

1

δ prq, 1s , a, Zq “ δ prq, 3s , a, Zq “

8

prp, 1s , γq si p P F prp, 2s , γq si p R F

Preguntas 1. Sea L un lenguaje. Si todas las palabras de L validan el Lema de Pumping para lenguajes independientes del contexto, ¿Podemos concluir que L es un lenguaje independendiente del contexto? 2. Sea L un lenguaje regular. Demostrar que todas las palabras de L validan el Lema de Pumping para lenguajes independientes del contexto. 3. Mostrar que L “ tap : p es número primou no es independente del contexto. Ayuda: . Asumir L es independiente del contexto, y n es la longitud dada por el Lema de Pumping. Sea m el primer primo mayor o igual que n, considerar α “ am y bombear m ` 1 veces. 4. Demostrar que un lenguaje regular intersección un lenguaje independiente del contexto es independiente del contexto. Ayuda: Definir el autómata de pila que lo reconoce. 5. Demsotrar que hay lenguajes que pueden ser reconocidos con un autómata con dos pilas pero no pueden ser reconocidos con un autómata con una sola pila. Ayuda: ver los ejemplo en esta clase.

9