Expresiones regulares y gramaticas

  • Published on
    04-Jul-2015

  • View
    1.329

  • Download
    0

Embed Size (px)

Transcript

  • 1. Robn Pea 12-0914Noel Gutirrez 12-0723

2. Lenguajes RegularesLos lenguajes regulares se llaman as porque sus palabras contienen regularidadeso repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1siguiente:L1 = {ab, abab, ababab, abababab, . . .}Definicon.- Un lenguaje L es regular si y slo si se cumple al menos una de lascondiciones siguientes:L es finito;L es la unin o la concatenacin de otros lenguajes regulares R1 y R2, L = R1 [R2 o L = R1R2 respectivamente.L es la cerradura de Kleene de algun lenguaje regular, L = R. 3. Definicin.- Sea un alfabeto. El conjunto ER de lasexpresiones regulares sobre contiene las cadenas en elalfabeto [ {^, +, , , (, ), } que cumplen con losiguiente:1. ^ y 2 ER2. Si 2 , entonces 2 ER.3. Si E1,E2 2 ER, entonces (E1+E2) 2 ER, (E1E2) 2ER, (E1)2 ER.Las comillas enfatizan el hecho de que estamosdefiniendo cadenas de texto, no expresiones matemticas 3.Es la misma diferencia que hay entre el carcter ASCII0, que se puede teclear en una terminal, y el nmero0, que significa que se cuenta un conjunto sin ningnelemento. 4. Las ER son simplemente formulas cuyo propsito esrepresentar cada una de ellas un lenguaje. As, elsignificado de una ER es simplemente el lenguaje que ellarepresenta.Por ejemplo, la ER representa el conjunto vaco {}.1. L() = ; (el conjunto vaco)2. L(^) = {"}3. L() = {}, 2 .4. L((RS) ) = L(R)L(S),R, S 2 ER5. L( (R+S) ) = L(R) [ L(S),R, S 2 ER6. L( (R) ) = L(R),R 2 ER 5. Ejemplo.- Obtener una ER para el lenguaje en el alfabeto {a, b, c} en que las palabras contienenexactamente una vez dos b contiguas. Por ejemplo, las palabras aabb, babba, pertenecen al lenguaje, pero noaaba, abbba ni bbabb.Para resolver este problema, expresamos primero la estructura de la ER de la manerasiguiente:< contexto1 > bb < contexto2 >Podemos ver que en esta expresin aparecen directamente las bb que deben estar en la ER, rodeadas por otras dosER, que son < contexto1 > y < contexto2 >. Ahora el problema es determinar que ER corresponden a < contexto1 > y , lo cual es un su problema del problema original. El lenguaje de < contexto1 > comprende a las palabrasque no tienen bb y adems no terminan en b. Esto es equivalente a decir que toda b esta seguida de una a o una c.Esto quiere decir que la ER de este contexto va ser de la forma:(. . . b(a + c) . . .)donde los detalles que faltan estn representados por las . . .. Lo que falta por considerares que puede haber cualquier cantidad de as o cs en el < contexto1 >, por lo que dichocontexto queda como:(b(a + c) + a + c)Similarmente se puede obtener la expresin para < contexto2 >, que es (a + c + (a + c)b),por lo que finalmente la ER del problema es:(b(a + c) + a + c)bb(a + c + (a + c)b) 6. 1. R + S = S + R, (R + S) + T = R + (S + T), R + = + R = R, R + R = R2. R ^ = ^ R = R, R = R = , (R S) T = R (S T)3. R (S + T) = R S + R T, (S + T) R = S R + T R4. R = R R = (R) = (^ + R), = ^ = "5. R = ^ + RR6. (R + S) = (R + S) = (RS) = (RS)R = R(SR) 6= R + S7. RR = RR, R(SR) = (RS)R8. (RS) = ^ + (R + S)S, (RS) = ^ + R(R + S)9. R = SR + T ssi R = ST, R = RS + T ssi R = TS 7. Por ejemplo, el conjunto de todas las palabras formadas por as ybs, que es el conjunto infinito {", a, b, ab, ba, aaa, aab, . ..}, puede ser representado mediante la cadena de caracteres{a, b}, que es una palabra formada por caracteres del alfabeto{a,b,{,},, , }. Como vemos en este ejemplo, una cadena decaracteres de 6 caracteres puede representar todo un lenguajeinfinito.Teorema.- El conjunto de los lenguajes en un alfabeto finito esincontable. 8. Teorema de Kleene.- Un lenguaje es regular si y solo si esaceptado por algn autmata finito. 9. Una posible solucin es el uso de las graficas de transicin. Estas ultimas son esencialmente AFN enque las etiquetas de las flechas tienen expresiones regulares, en lugar de palabras. Las graficas detransicin (GT) son por lo tanto quntuplos (K,,, s, F) en donde 2 K ER K.Los AFN son un subconjunto propio de las GT, puesto que las palabras en las etiquetas de un AFNpueden ser vistas como expresiones regulares que se representan as mismas. 10. Un procedimiento para hacerlo consiste en ireliminando gradualmente nodos de unaGT, que inicialmente es el AFN que se quieretransformar, hasta que nicamente queden unnodo inicial y un nodo nal. 11. 1. El primer paso en este procedimiento consiste en aadir al autmata nito un nuevo estado inicial i, mientras que el antiguo estado inicial q0 deja de ser inicial, y un nuevo estado nal f, mientras que los antiguos estados nales qi F dejan de ser nales;2. El segundo paso consiste en eliminar nodos intermedios en la GT. 12. Una gramtica es un conjunto de reglas paraformar correctamente las frases de un lenguaje; astenemos la gramtica del espaol, del francs, etcUna regla es una expresin de la forma , endonde tanto como son cadenas de smbolos endonde pueden aparecer tanto elementos del alfabeto como unos nuevos smbolos, llamados variables.Los smbolos que no son variables son constantes. 13. Formalizamos estas nociones con las siguientesdeniciones:Denicin.- Una gramtica regular es uncudruplo (V, , R, S) en donde:V es un alfabeto de variables, es un alfabeto de constantes,R, el conjunto de reglas, es un subconjunto nitode V (V ).S, el smbolo inicial, es un elemento de V 14. Teorema.- La clase de los lenguajes generadospor alguna gramtica regular es exactamentela de los lenguajes regulares. Limitaciones de los lenguajes regularesLos AF estn limitados a los estados de quedisponen como nico medio para recordar laserie de smbolos recibidos hasta un momento dado. 15. Teorema.- Si L es un lenguaje regularinnito, entonces existen cadenas x, y, z talesquey 6= , y xynz L, para algn n 0.Lo que este resultado establece esque, suponiendo que cierto lenguaje esregular,entoncesforzosamente dicholenguaje debe contener palabras en que unasubcadena se repite cualquier nmero de