Propiedades de las expresiones regulares (1) regulares ?· • Expresiones regulares equivalentes: aquellas…

  • Published on
    30-Aug-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Csar Ignacio Garca Osoriorea de Lenguajes y Sistemas Informticos</p><p>Universidad de BurgosFebrero, 1999 Lenguajes regulares y autmatas finitos 2Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Conjuntos y expresiones regulares Conjunto regular: Cualquier conjunto de cadenas que se pueda </p><p>formar mediante las operaciones de unin, concatenacin y cierre. Las expresiones regulares se utilizan para denotar conjuntos </p><p>regulares y se definen del siguiente modo recursivo (dado un alfabeto : la expresin regular que denota el conjunto {} a , a es una expresin regular que designa al conjunto regular {a} Si y son expresiones regulares que designan los conjunto regulares C y </p><p>C respectivamente, entonces: ()|() es la expresin regular que designa al conjunto regular C C ()() es la expresin regular que designa al conjunto regular CC ()* es la expresin regular que designa al conjunto regular C* () es la expresin regular que designa al conjunto regular C</p><p> es la expresin regular que representa la conjunto vaco (que es regular) Ninguna otra cosa es un expresin regular.</p><p>Lenguajes regulares y autmatas finitos 3Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Propiedades de las expresiones regulares (1)</p><p> Expresiones regulares equivalentes: aquellas que an siendo distintas representan el mismo lenguaje.</p><p> Algunas propiedades de las e.r. en cuanto a su equivalencia son: r|s=s|r (la unin o seleccin es conmutativa) r|(s|t) = (r|s)|t (la seleccin es asociativa) (rs)t=r(st) (la concatenacin es asociativa) r(s|t)=rs|rt (la concatenacin es distributiva por la izquierda </p><p>respecto de la unin) (r|s)t=rt|st (la concatenacin es distributiva por la derecha </p><p>respecto de la unin)Lenguajes regulares y autmatas finitos 4Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Propiedades de las expresiones regulares (2)</p><p> r=r =r ( es el elemento neutro de la concatenacin) |r = r| = r ( es el elemento neutro de la unin) (r*)*=r* (el cierre es idempotente) r* = r*r* = (|r)* = r*| = r*(r*|) = (r|)r* = |rr* = |r*r (r*|s*)* = (r*s*)* = (r|s)* = (r*s)*r* = r*(sr*)* r(sr)* = (rs)*r *=*= r+ = rr* = r*r r*=r+ | + = r = r = </p><p> (r*s)* = | (r|s)*s (rs*)* = | r(r|s)* r* (r|t)* rn r* si r t entonces r* t* si r1t1 y r2t2 entonces r1r2 t1t2</p></li><li><p>Lenguajes regulares y autmatas finitos 5Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Definicin regular sobre </p><p> Conjunto de definiciones de la forma:d1 r1 donde r1 es una expresin regular sobre d2 r2 donde r2 es una expresin regular sobre d1d3 r3 donde r3 es una expresin regular sobre d1d2..... . . ...di ri donde ri es una expresin regular sobre ij=1dj..... . . ...dn rn donde rn es una expresin regular sobre nj=1dj</p><p> Es decir, es una especie de gramtica en la que no se permiten definiciones recursivas.</p><p>Lenguajes regulares y autmatas finitos 6Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Autmatas (1)</p><p> Autmata finito determinista: es una quintupla (,Q, f, q0, F ), donde: es un alfabeto de entrada. QQQQ es un alfabeto de estados. f es la funcin de transicin:</p><p>f : Q Q q0 es el estado inicial. FFFF Q es el conjunto de estados finales o estados </p><p>de aceptacin</p><p>Lenguajes regulares y autmatas finitos 7Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Autmatas (2)</p><p> Autmata finito no determinista: es una quintupla ( ,Q, f, q0, F ), donde: es un alfabeto de entrada. QQQQ es un alfabeto de estados. f es la funcin de transicin:</p><p>f : Q ( ) P(Q) q0 es el estado inicial. FFFF Q es el conjunto de estados finales o estados </p><p>de aceptacin</p><p>Lenguajes regulares y autmatas finitos 8Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Autmatas (3)</p><p> La parte fundamental de un autmata finito es su funcin de transicin por eso es habitual representarlo mediante una tabla que da dicha funcin o mediante un grafo </p><p>estados = nodos transiciones = arcosestados finales = nodo con doble circuloestado inicial = nodo con flecha de entrada</p><p>a, b, c</p><p>c</p><p>b</p><p>q3</p><p>a</p><p>q2</p><p>c</p><p>a</p><p>ba</p><p>b, c</p><p>q0 q1</p><p>a b cq0 q0 q1 q2</p><p>q1 q3 q2 q2(q2) q3 q3 q3(q3) q3 q2 q2</p></li><li><p>Lenguajes regulares y autmatas finitos 9Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Autmatas (4)</p><p> Extensin de f a palabras: la funcin f toma como argumentos un estado y un carcter, pero se puede definir una funcin que tome un estado y una palabra:f~: Q * Q e x*</p><p>f~(q, e) = f (q, e) f</p><p>~(q, ex) = f</p><p>~(f (q,e), x)</p><p>La funcin f~(q, w), da el estado al que se puede llegar</p><p>partiendo de q y siguiendo las transiciones segn w.</p><p> El lenguaje reconocido por un autmata M= (,Q, f, q0, F) se define como:</p><p>L(M)={w*: f~(q0,w)F} AFD</p><p>L(M)={w*: f~(q0,w)F } AFND</p><p>Lenguajes regulares y autmatas finitos 10Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Simulacin de un AFDs q1;c sgtecar();while c e.o.f dobegin</p><p>s mueve(s,c);c sgtecar();</p><p>endif sF then return SI else return NO</p><p>mueve(s,c) es una funcin que implementa la funcin de transicin, dado un estado y un carcter nos devuelve el estado siguiente</p><p>sgtecar() es una funcin que accede al siguiente carcter de la cadena de entrada</p><p>Lenguajes regulares y autmatas finitos 11Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Simulacin de un AFNDmueve(s,c) funcin de transicin</p><p>sgtecar() accede al siguiente carcter de la entrada</p><p>cerr- (s) conjunto de estados a los que se puede llegar a partir de ssiguiendo arcos etiquetados con </p><p>S cerr-({s0 });c sgtecar();while c e.o.f dobegin</p><p>S cerr-(mueve(S,c));c sgtecar();</p><p>endif SF then return SI else return NO</p><p>Lenguajes regulares y autmatas finitos 12Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Paso de un AFND a un AFD cerr-(q) = {f</p><p>~(q, n)}{q}. Es decir el conjunto de estados a los que puedo </p><p>llegar a partir del estado q mediante transiciones (sin consumir entrada) cerr-(T)= qT cerr-(q) Algoritmo: Construccin de subconjuntos</p><p>D cerr-(q0);while haya un estado T sin marcar en D do</p><p>marcar T;for cada smbolo de entrada a do</p><p>U cerr-(mueve(T, a));if UD then aadir U sin marcar a DtranD[T, a] U</p><p>AFND( ,Q, f, q0, F ) AFD( ,D, tranD, cerr-(q0), F ) F={UD: UF }</p></li><li><p>Lenguajes regulares y autmatas finitos 13Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Teoremas de anlisis y sntesis</p><p> Teorema de sntesis: Todo conjunto regular es un lenguaje aceptado por un reconocedor finito. e.r AFD Procedimientos:</p><p> Mtodo de Thompson Mtodo de las derivadas Mtodo de Aho-Sethi-Ullman</p><p> Teorema de anlisis: Todo lenguaje aceptado por un reconocedor finito es un un conjunto regular. AFD e.r Procedimientos:</p><p> Mtodo 1 Mtodo de las ecuaciones caractersticas</p><p>Lenguajes regulares y autmatas finitos 14Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Thompson (1)</p><p>Lenguajes regulares y autmatas finitos 15Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Thompson (2)</p><p>Lenguajes regulares y autmatas finitos 16Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las derivadas (1)</p><p> Consideremos una expresin regular , que designa un conjunto regular L, y consideremos el conjunto Leformado por todas las cadenas de L que empiezan por un determinado smbolo e. Definimos el cociente izquierdo de L entre e, denotado L\e, como el conjunto resultante de suprimir e en todas las cadenas de Le.</p><p>L\e={w : ew L}y definimos la derivada de respecto al smbolo e, </p><p>denotado De(), como la expresin regular de L\e.</p></li><li><p>Lenguajes regulares y autmatas finitos 17Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las derivadas (2) Algunas propiedades de las derivadas as </p><p>definidas son: De1(e2) = si e1=e2 si e1e2 De() = De() = D()= Dew()=Dw[De()] Dwe()=De[Dw()] De(|)=De()|De() De()=De() | ()De() donde ()= si L si L De(*)=De()*</p><p>Lenguajes regulares y autmatas finitos 18Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las derivadas (3)Algoritmo de sntesis (Brozozowaki, 1962) Para construir un reconocedor del lenguaje denotado por la </p><p>expresin regular, se puede seguir el siguiente procedimiento Calcular {Dw(): w*} El estado inicial es q1=; los otros son las diferentes </p><p>Dw() La funcin de transicin es f(, e)= De(); </p><p>f(Dw(), e)= Dwe(); El conjunto de estado finales es </p><p>F={Dw(): L(Dw())}</p><p>Lenguajes regulares y autmatas finitos 19Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(1)</p><p> Construir la e.r. ampliada $ $ Obtener el rbol sintctico de $ Responder a las preguntas:</p><p> Que letras pueden aparecer como primera letra de la e.r. representada por cules como ltimas?</p><p> Supuesto que yo se que letra acaba de aparecer, que letras pueden venir a continuacin en las palabras representadas por ?</p><p> La idea es tratar de numerar la posicin de las letras que aparecen en la e.r. Una vez que tengo el rbol puedo hacer una numeracin, lo cual me da una ordenacin parcial. Se establece una equivalencia entre los estados significativosdel autmata y las posiciones del rbol (nodos hoja).</p><p>Lenguajes regulares y autmatas finitos 20Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(2)</p><p> Permite construir directamente un AFD a partir de una expresin regular aumentada ($ $).</p><p> Primero se construye un rbol sintctico T para $ con las posiciones de las hojas numeradas y despus se calculan cuatro funciones: anulable, primera-pos, ltima-pos y siguiente-pos haciendo recorridos sobre T.</p><p> Por ltimo se construye el AFD a partir de la funcin siguiente-pos. Las funciones anulable, primera-pos y ltima-pos se definen sobre los nodos del rbol sintctico y se usan para calcular siguiente-pos, que est definida en el conjunto de posiciones de las hojas en el rbol.</p></li><li><p>Lenguajes regulares y autmatas finitos 21Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(3)</p><p> La nocin de una posicin concordando con un smbolo de entrada ser definida en cuanto a la funcin siguiente-pos en posiciones del rbol sintctico. Si i es una posicin, siguiente-pos(i) es el conjunto de posiciones j tales que hay alguna cadena de entrada ...cd... Tal que i corresponde a esta aparicin de c y j a esta aparicin de d.</p><p> Para calcular la funcin siguiente-pos, es necesario conocer qu posiciones pueden concordar con el primer o ltimo smbolo de una cadena generada por una determinada subexpresin de una expresin regular. Para esto es tambin necesario conocer qu nodos son las races de las subexpresiones que generan lenguajes que incluyen la cadena vaca (nodos anulables)</p><p>Lenguajes regulares y autmatas finitos 22Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(4)</p><p>Nodo anulable(n) primera-pos(n) ltima-pos(n)n es una hoja con smbolo true </p><p>false {i} {i}n es una hoja con la posicin i</p><p>c1 c2</p><p>nanul(c1)anul(c2)</p><p>if anul(c1) thenpripos(c1)pripos(c2) else pripos(c1)</p><p>if anul(c2) thenltpos(c1)ltpos(c2) else ltpos(c2)</p><p>*</p><p>c1</p><p>ntrue pripos(c1) ltpos(c1)</p><p>anul(c1)anul(c2) pripos(c1)pripos(c2) ltpos(c1)ltpos(c2)|</p><p>c1 c2</p><p>n</p><p>Lenguajes regulares y autmatas finitos 23Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(5)</p><p> La funcin siguiente-pos(i) indica qu posiciones pueden seguir a la posicin i en el rbol sintctico. Dos reglas definen todas las formas en que una posicin puede seguir a otra: Si n es un nodo-cat con hijo izquierdo c1 e hijo derecho c2, e i</p><p>es una posicin dentro de ltima-pos(c1), entonces todas las posiciones de primera-pos(c2) estn en siguiente-pos(i).</p><p>iltima-pos(c1) siguiente-pos(i) primera-pos(c2) Si n es un nodo-ast, e i es una posicin dentro de ltima-pos(n), </p><p>entonces todas las posiciones de primera-pos(n) estn en siguiente-pos(i)</p><p>iltima-pos(c1) siguiente-pos(i) primera-pos(c1)</p><p>Lenguajes regulares y autmatas finitos 24Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de Aho-Sethi-Ullman(6)</p><p> Algoritmo para obtener el AFD a partir de siguiente-posD primera-pos (raz);while haya un estado T sin marcar en D do</p><p>marcar T;for cada smbolo de entrada a do</p><p>U siguiente-pos(p);</p><p>if (UD) (U) then aadir U sin marcar a DtranD[T, a] U</p><p>endend</p><p>AFD( ,D, tranD, primera-pos(raz), F ) F={UD: p U y p la posicin de $}</p><p>p etiqueta una hoja con smbolo apT</p></li><li><p>Lenguajes regulares y autmatas finitos 25Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Demostracin del teorema de anlisis (1)</p><p> Sea un AFD (,Q, f, q1, F ), con n estados, Q={q1, q2, ...,qn}, con estados finales F={qf1, qf2, ...,qfr}, el lenguaje aceptado es:</p><p>L(R)={w| f~(w, q1)F}</p><p>o de forma equivalenteL(R)= {R1j|qjF}</p><p>con Rij={x| f~(x, qi)= qj} (conjunto de cadenas que </p><p>llevan qi del estado al estado qj). Basta entonces demostrar que los Rij son conjuntos regulares.</p><p>Lenguajes regulares y autmatas finitos 26Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p> Se define Rkij (0 k n) como el conjunto de cadenas que llevan del estado qi al estado qi sin pasar por ningn estado ql tal que l &gt; k.</p><p> Vamos a demostrar por induccin que los Rkij son conjuntos regulares: Para k=0, esta claro que R0ij es regular Supuesto que Rk-1ij es regular se tiene que:</p><p>Rkij = Rk 1ij Rk 1ik (Rk 1kk )*Rk 1kj por tanto, Rkij es regular para todo k, y, en</p><p>particular, Rij = Rnij es regular. Y L(R) es regular</p><p>Demostracin del teorema de anlisis (2)</p><p> Se define Rkij (0 k n) como el conjunto de cadenas que llevan del estado qi al estado qj sin pasar por ningn estado ql tal que l &gt; k.</p><p> Vamos a demostrar por induccin que los Rkij son conjuntos regulares: Para k=0, esta claro que R0ij es regular Supuesto que Rk-1ij es regular se tiene que:</p><p>Rkij = Rk 1ij Rk 1ik (Rk 1kk )*Rk 1kj </p><p>Lenguajes regulares y autmatas finitos 27Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Demostracin del teorema de anlisis (3)</p><p>q jq i</p><p>qk</p><p>R k-1ij</p><p>R kij</p><p>R k-1ik R k-1kj</p><p>Rk-1kkLenguajes regulares y autmatas finitos 28Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las ecuaciones caractersticas (1)</p><p> La ecuacin caracterstica de un estado qirepresenta el conjunto de cadenas aceptadas por el estado qi</p><p>i= aijj (+ )</p><p>q ja ij</p><p> j i</p><p>q iqo q f</p><p>jS(qi) S(qi) representa el conjunto de ndices j para los cuales qj es un estado siguiente de qi</p></li><li><p>Lenguajes regulares y autmatas finitos 29Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las ecuaciones caractersticas (2)</p><p> Otra forma de definir la ecuacin caracterstica de un estado es:</p><p> Donde aij, bk , S(qi) representa el conjunto de argumentos j para los cuales </p><p>qj es un estado siguiente de qi , Sf(qi)S(qi) son slo aquellos argumentos j para los cuales qj</p><p>es un estado siguiente de qi y adems qjF (qi) = si qi = q0 y q0 F</p><p>++=)( )(</p><p>)(i ifqSj qSk</p><p>ikjiji qba </p><p>Lenguajes regulares y autmatas finitos 30Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Mtodo de las ecuaciones caractersticas (3)</p><p>Una vez que se obtiene los sistemas de ecuaciones para cada estado, se deben intentar resolver las ecuaciones de cada estado, de manera que tengan la forma xi=Axi+B donde A, xiB, que es a lo que se denomina ecuacin caracterstica. Y se resuelve usando el resultado que da el lema de Arden.</p><p>Lema de Arden: Una ecuacin de la forma X=AX+B, donde A y B tiene una solucin nica X=A*B.</p><p>Lenguajes regulares y autmatas finitos 31Csar Ignacio Garca Osorio. Universidad de Burgos.</p><p>Lema de bombeo (1)</p><p> Para todo lenguaje L regular existe una constante n, tal que para toda palabra zL (|z|n) existen u, v, w, z=uvw,|u...</p></li></ul>