Transcription
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoGramáticas independientes del contextoAUTÓMATAS Y LENGUAJES FORMALESLENGUAJES INDEPENDIENTES DELCONTEXTO Y AUTÓMATAS DE PILAUna gramática G hΣ, Γ, S, i es independiente del contexto siitodas las reglas de producción tienen una de las dos siguientes formasA αdonde A Γ.Francisco Hernández QuirozCFGUn lenguaje L es independiente del contexto sii existe una gramáticaG CFG tal queL L(G).Posgrado en Ciencia e Ingeniería de la ComputaciónCFLAutómatas y Lenguajes Formalesdesignará el conjunto de gramáticas independientes del contexto.El lenguaje generado por G se denotará con L(G).Departamento de MatemáticasFacultad de Ciencias, UNAME-mail: fhq@ciencias.unam.mxPágina Web: www.matematicas.unam.mx/fhqFrancisco Hernández QuirozA ,Leng. independientes del contexto1 / 36es el conjunto de lenguajes independientes del contexto.Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoEjemplosLeng. independientes del contexto2 / 36Leng. independientes del contexto4 / 36Otras definiciones IConsidérese una derivación1α0 α1 · · · αn .Lenguaje de palindromas. Sea GP h{a, b}, {S}, S, P i, dondeEsta derivación presupone reglas de producciónS P aSa bSb .2A1 β1 . . . An βnLenguaje de paréntesis. Sea Sea GD h{(, )}, {S}, S, D i, con lassiguientes reglasS D (S) SS .tales queαi γi Ai ηiαi 1 γi βi ηi .Esta derivación será por la izquierda sii para todo i nγi γi 1Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto3 / 36Francisco Hernández Quirozγi Σ Autómatas y Lenguajes Formales
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoOtras definiciones IIOtras definiciones IIIy será por la derecha siiηi ηi 1η i Σ .Una producción es terminal sii no contiene símbolos no terminales del ladoderecho.Una producción es una regla- sii su lado derecho es .Una producción es unitaria sii es de la forma de la forma A B, conA, B Γ.Una gramática es propia sii no contiene regla- ni reglas unitarias.Una gramática es no ambigua sii α L(G), α tiene exactamente unaderivación por la izquierda (o por la derecha).Un lenguaje es no ambiguo sii existe una gramática no ambigua que logenere. De lo contrario, será inherentemente ambiguo.Una gramática es pulcra sii(a) A Γ . L(A) 6 ;(b) A Γ . α, β Σ . S αAβ o S A.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto5 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoParéntesis balanceadosLeng. independientes del contexto6 / 36Lenguajes de DyckEl lenguaje de paréntesis se puede generalizar a los lenguajes de Dyck. SeaA un alfabeto de símbolos no terminales y sea Ā una copia de A, es decir:La gramática GD genera el lenguaje de paréntesis balanceados, es decir,α L(GD ) sii1A(α) C(α);2C(β) A(β)(i) A Ā (ii) existe una biyección de A a Ā.Por ejemplo, si A {(}, entonces Ā {)}.El lenguaje de Dyck sobre A es el lenguaje generado por las reglas deproducción:S a1 S ā1 · · · an S ān SS , β . γ . α βγ;donde A(α) y C(α) son el número de paréntesis que abren y cierran queaparecen en α, respectivamente.Demostración. Por inducción en la derivación de S α.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contextodonde A {a1 , . . . , an } y āi Ā es la copia de ai . Este lenguaje sedenotará con DA .Si A n, una notación alternativa es Dn .7 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto8 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoFormas normales de Chomsky y de GreibachEjemplosLos conjuntos de producciones siguientes tienen forma normal de Chomskyy de Greibach (respectivamente)Sea G hΣ, Γ, S, i un gramática. G tiene forma normal de Chomsky(CNF) sii todas las producciones tiene la formaA BCS AB AC SSA a,C SBS (B (SB (BS (SBSdonde A, B, C Γ y a Σ.A (B )B )y generan el lenguaje de paréntesis balanceados.En cambio, G tiene forma normal de Greibach (GNF) sii todas lasproducciones tienen la formaLas producciones siguientes generan el lenguaje de palindromasS AA BB AC BDA bB1 · · · BkC SAS aA aSA bB bSBA aD SBA aB bB bcon 0 k, b Σ y B1 , . . . , Bk Γ.Con excepción en ambos casos de .Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto9 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoTodas las CFG tienen equivalente en CNF o GNFLeng. independientes del contexto10 / 36Lema de gramáticas propias ISea G CFG. Entonces, existe una gramática propia G0 tal queTeorema. Sea G CFG. Entonces existen GC , GG CFG tales que tienenforma normal de Chomsky y de Greibach, respectivamente, yL(G0 ) L(G) { }.Demostración. Sea 0 la relación mínima queL(GC ) L(GG ) L(G) { }.(i) contiene a ;(ii) si A 0 αBβ y B , entonces A 0 αβ(iii) si A 0 B y B 0 γ, entonces A 0 γ.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto11 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto12 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoLema de gramáticas propias IIY seaG0Transformación a forma normal de Chomsky CFG como G, pero con las reglas de producción 0 .Una vez que contamos con una gramática propia G00 , podemos construir laFNC :EntoncesL(G) L(G0 )Obviamente, L(G) L(G0 ). Para L(G0 ) L(G), baste observar que todaderivación en G se puede realizar en G0 , salvo tal vez en dos pasos.Sea ahora G00 como G0 pero con la relación 00 que prescinde de lasproducciones unitarias y - que existan en 0 . Entonces1Para cada a Σ, introducimos nuevos no terminales Aa y reglas deproducción Aa a.2Sustituimos los terminales por los no terminales del punto anterior entodas las reglas de G00 que no tengan FNC todavía.3Dada una regla A B1 . . . Bk (K 2), introducimos un nuevoterminal C1 y las reglasL(G00 ) L(G0 ) { } L(G) { }.A B1 C1Esta última afirmación se demuestra considerando que las derivaciones delongitud mínima en G0 prescinden de producciones- y unitarias.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto13 / 36C1 B2 . . . Bk .4Repetimos este procedimiento hasta tener sólo reglas con dos noterminales del lado derecho.5Eliminamos las reglas del punto anterior que no tengan FNC.Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoTransformación a forma normal de GreibachLenguaje de paréntesis. Empezamos con forma normal de Chomsky:S AB AC SSRX ,x {β Γ X L xβ}.A (B ).RS,( (B C)S Este lenguaje es regular. Sea GX ,x una gramática lineal por la derechaque lo genere. Sea SX,x el símbolo inicial de esta gramática.Entonces, sustituimos las reglasRC,( (B C)S BRA,( { }RB,) { }por reglasEstas producciones nos generan los lenguajes anteriores:A xSX ,x Y ,SS,( BX CXSC,( BY CYSA,( SB,) y agregamos las producciones y símbolos no terminales de GX,x anuestra gramática.Eliminamos las reglas- .Francisco Hernández QuirozC SBTenemos ahora los siguientes lenguajes RX ,xA XY314 / 36Ejemplos ISea GC una gramática en FNC. Para convertirla a FNG:1Para cada X Γ, considérese el lenguaje2Leng. independientes del contextoAutómatas y Lenguajes FormalesLeng. independientes del contexto15 / 36Francisco Hernández QuirozX SX Y SY BZAutómatas y Lenguajes FormalesZ Leng. independientes del contexto16 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoEjemplos IITeorema del bombeo ISea L CFL. Entonces, existe k N tal que para toda α L, si k α ,entoncesα βγηθφyγθ 6 Entonces, tenemos las reglas nuevasS (SA,( B (SA,( C (SS,( SSS,( )SB,) X (SC,( XSC,( )SB,) Y (SC,( YSA,( y para toda i NC (SS,( BX (SS,( X Y (SS,( Y )SB,) ZSB,) A (B )Z βγ i ηθi φ L.Demostración.Sea G CFG en FNC y L(G) L .Sea Γ el alfabeto de símbolos no terminales de G, con Γ n y seak 2n 1 .Entonces, el árbol sintáctico de toda cadena de longitud igual osuperior a k debe tener profundidad de n 1 al menos.Entonces en un camino de longitud máxima de la raíz a las hojas debeaparecer dos veces, al menos, el mismo no terminal.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto17 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoTeorema del bombeo IILeng. independientes del contexto18 / 36EjemploConsidérense los siguientes árboles de derivación:SAEste no terminal puede usarse para definir las cadenas γ y θ.BVAaeXbgWchfdÁrbol de la cadena βγηθφ abcdefghFrancisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto19 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto20 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoDefinición Ejemplos Lenguajes de Dyck Formas normales T. del bombeoAplicacionesSAVeXVgWAcWComo con los lenguajes regulares, este teorema se puede utilizar parademostrar que un lenguaje dado no es independiente del contexto. Ejemplos:Bh{an bn c n },por una aplicación directa del teorema, yf{αα}dpues los CFL y los regulares son cerrados bajo intersección yAaeXbcf{an bm an bm } {αα} L(a b a b )dy, obviamente, {an bm an bm } no es independiente del contextoÁrbol de la cadena βγ 2 ηθ2 φ abcdefcdefghFrancisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto21 / 36Francisco Hernández QuirozCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Equivalencia DeterminismoDefinición Equivalencia DeterminismoAutómatas de pilaAutómatas y Lenguajes FormalesLeng. independientes del contexto22 / 36Lenguajes aceptados por NPDAUna configuración de un autómata A NPDA es una terna (q, α, β) dondeq QUn autómata de pila no determinista A está formado porun conjunto de estados Q;α Σ un alfabeto de entrada Σ;β Γ un alfabeto de pila Γ;La configuración inicial es (s, α, ). Definiremos ahora una relación entreconfiguraciones:una relación de transición δ (Q (Σ { }) Γ) (Q Γ )un estado inicial s;un símbolo inicial de la pila ;si δ((q, a, B), (r, η)) entonces (q, aα, Bβ) (r, α, ηβ)un subconjunto de estados finales F Q.si δ((q, , B), (r, η)) entonces (q, α, Bβ) (r, α, ηβ)Llamaremos NPDA a los autómatas de pila no deterministas.El lenguaje aceptado por un A NPDA esL(A) {α Σ f F . (s, α, ) (f , , β)}Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto23 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto24 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Equivalencia DeterminismoDefinición Equivalencia DeterminismoAceptación por pila vacíaTeorema de equivalencia entre CFG y NPDA I(a) Sea G CFG. Entonces, existe A NPDA tal queL(G) L(A).Una definición alternativa del lenguaje aceptado por un A NPDA es(b) Sea A NPDA. Entonces, existe G CFG tal queL(A) {α Σ (s, α, ) (q, , )}L(G) L(A).Ambas definiciones son equivalentes y puede construirse un A0 NPDA queacepte por pila vacía el mismo lenguaje que un A NPDA que acepte porestado final (y viceversa).Demostración(a) Sea G hΣ, Γ, S i en FNG. SeaA ({q}, Σ, Γ, δ, q, S, q),dondeδ((q, a, A), (q, B1 · · · Bk ))Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto25 / 36Francisco Hernández QuirozCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesDefinición Equivalencia DeterminismoDefinición Equivalencia DeterminismoTeorema de equivalencia entre CFG y NPDA IIsiiA nG αγ.α L(G) sii S G αsii (q, α, S)(q, , )26 / 36δ no puede eliminar de la pila a , es decirδ(q, a, ) (r, α ).(b) Se demuestra primero que para todo A NPDA existe un A0 NPDA conun solo estado tal queL(A) L(A0 )La aceptación es por estados finales. La aceptación por pila vacíadefine un conjunto de lenguajes diferente.Un ejemplo de un lenguaje en CFL pero no en DCFL esy una vez construido A0 , los argumentos del caso (a) se pueden aplicar ensentido inverso.Autómatas y Lenguajes FormalesLeng. independientes del contextoδ : Q Σ { , a} Q Γ .sii α L(A).Francisco Hernández QuirozAutómatas y Lenguajes FormalesA diferencia de los lenguajes regulares, la clase CFL no determinista esestrictamente mayor que la determinista (DCFL).Un autómata determinista de pila D (Q, Σ, Γ, δ, , a, s, F ) incluye elsímbolo especial a que sirve para indicar el final de la cadena deentrada.Las transiciones están indicadas por la funciónEntonces AA aB1 · · · Bk .DeterminismoSi puede demostrar por inducción en la longitud de las derivaciones (por laizquierda) que(q, αβ, A) nA (q, β, γ)siiLeng. independientes del contexto{a, b} {αα α {a, b} }27 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto28 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesChomsky-Schützenberger Reconocimiento ParikhChomsky-Schützenberger Reconocimiento ParikhEl teorema de Chomsky y Schützenberger IEl teorema de Chomsky y Schützenberger IISea L CFL. Entonces existen n N, R REG y un homomorfismo h talqueL h(Dn R).y sean1Nota: un homomorfismo h : Σ Γ es una función tal queh(αβ) h(α)h(β).L(G0 ) cumple además con las siguientes restricciones adicionales:si π A BC1Para toda π , el símbolosi π A aAutómatas y Lenguajes FormalesLeng. independientes del contexto29 / 36Francisco Hernández QuirozCFG Autómatas de pila Algunos teoremas útilesChomsky-Schützenberger Reconocimiento ParikhChomsky-Schützenberger Reconocimiento ParikhEl teorema de Chomsky y Schützenberger IIINingún3Si π A BC entonces30 / 36está seguido de ρ[ .1[π1está seguido de ρ[ , con ρ B β.Si π A BC entoncesAnálogamente para π .5Leng. independientes del contextoEl teorema de Chomsky y Schützenberger IV2[42está seguido de π[ .n2π1]πAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útiles2]2Se puede definir fácilmente un isomorfismo con un lenguaje Dn (con un parde tipos de paréntesis por cada regla en ). Obviando el isomorfismo, esclaro queL(G0 ) Dn .π, ρ, σ, . . .Francisco Hernández Quiroz2G0 hΣ0 , Γ, S, 0 iDemostración. Sea G hΣ, Γ, S, i en FNC. Asignaremos letras griegasminúsculas a las producciones de G:Definiremos nuevas producciones 11 22 A π[ B π] π[ C π]π0 1 1 2 2 A π[ π] π[ π]1Σ0 { [ , ] , [ , ] π }π π π π 0 {π 0 π }1Si π A a, entonces1[πestá seguido por la cadenaSi A G0 α, entonces α comienza con1[π1 2 2] [ ]πππ.para alguna π A γ.1h( [ ) aπ0RA {α Σ α satisface 1–5}Leng. independientes del contexto21y22h( ] ) h( [ ) h( ] ) .πππEl teorema se sigue directamente de esta definición.Lema. A G0 α sii α Dn RA .Suponiendo que el lema anterior es verdadero, entonces definimos elhomomorfismo0h : Σ Σ .Autómatas y Lenguajes Formales2Si π A a entoncesConsidérese el siguiente lenguaje regular:Francisco Hernández Quiroz1h( [ ) h( ] ) h( [ ) h( ] ) .ππππ31 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto32 / 36
CFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesChomsky-Schützenberger Reconocimiento ParikhLema A G0α sii α Chomsky-Schützenberger Reconocimiento ParikhDn RAAlgoritmo de Cocke, Kasami y YoungerEs un algoritmo para decidir de manera eficiente si una cadenapertenece a un CFL.Sea L un CFL y sea G hΣΓ, S, i una CFG en forma normal deChomsky tal queL(G) L.Demostración. Por inducción en n para la dirección .Para el caso inverso, por inducción en la longitud de las cadenas enDn RA . Basta considerar queα 1[β1 2] [γ2]π ππ πSea α L con longitud n. Sean 0 i j n y seay analizar los dos casos posibles para π, a saber, A BC o bien A a.En el primer caso, por hipótesis inductiva,B G0 βyαi,jla subcadena de α que va de la posición i 1 a la j.Sea Ti,j Γ el conjunto de no terminales que generaron αi,j .El algoritmo calcula el valor de todos los Ti,j de manera inductiva. Enparticular, S T0,n si S G α.El algoritmo es O(pn3 ), p el número de producciones en G.C G0 γy además β y γ satisfacen las condiciones 1–5. El segundo caso es aún mássimple.Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto33 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesCFG Autómatas de pila Algunos teoremas útilesCFG Autómatas de pila Algunos teoremas útilesChomsky-Schützenberger Reconocimiento ParikhChomsky-Schützenberger Reconocimiento ParikhLeng. independientes del contexto34 / 36El teorema de Parikhfor i : 0 to n 1 doTi,i 1 : ;for A a G doif a αi,i 1 thenTi,i 1 : Ti,i 1 {A}Sean Σ {a1 , . . . , an }, α Σ y a Σ.Sea #a(α) es el número de apariciones del símbolo a en α.El mapa de Parikh es la función ψ : Σ Nn definida porψ(α) (#a1 (α), . . . , #an (α)).for m : 2 to n dofor i : 0 to n m doTi,i m : ; for j : i 1 to i m 1 dofor A BC G doif B Ti,j C Tj,i m thenTi,i m : Ti,i m {A}Sea (0, . . . , 0).Entonces, Nn y : Nn Nn N (suma por coordenadas) forman unmonoide, i.e., un conjunto con una operación binaria asociativa y unelemento neutro de esta operación, a saber, 0̄.Además, Σ y · también forman un monoide.ψ es un homomorfismo entre Σ y Nn .Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto35 / 36Francisco Hernández QuirozAutómatas y Lenguajes FormalesLeng. independientes del contexto36 / 36
A un alfabeto de símbolos no terminales y sea A una copia de A, es decir: (i) A \A ; (ii)existe una biyección de A a A . Por ejemplo, si A f(g, entonces A f)g. El lenguaje de Dyck sobre A es el lenguaje generado por las reglas de producción: S !a1Sa 1 jj anSa n jSS j , donde A fa1,:::,angy a i 2A es la copia de ai. Este .
