Unidad II.-Expresiones Regulares matameticas avanzadas

Temas de matematicas avanzadas donde se explican las expresiones regulares

1. Unidad II Expresiones Regulares Tecnológico Nacional de México M.A.S.C. Arturo Iván Grajales Vázquez.

2. 2.1. Definición formal de una ER.

3. Las Expresiones regulares permiten especificar la construcción de analizadores léxico que son las primera etapas en la construcción de un lenguaje de programación implementado como compilador o interprete.

4. 2.2.- Operaciones.

5. Por convenio de notación, las expresiones regulares se define con las siguientes propiedades. Propiedad Representación formal Significado Unión L∪M { x|x esta en L o x esta en M} Concatenación LM { xy|x esta en L y y esta en M} Cerradura de Kleene L * L* significa “ cero o mas concatenacion de L ” Cerradura positiva L + L + significa “ una o mas concatenaciones de L ” U ∞ i=0 L*= L i U ∞ i=1 L + = L i

6. Precedencia en las expresiones regulares. Para simplificar la notación de una expresión regular, las reglas en el convenio de precedencia queda como sigue: Cerradura *, + Concatenación Unión Alfabeto Expresión Expresión simplificada cadena ∑={a} {a} {a}* a a* a ε , a,aa,aaa,aaaa ,…… ∑={ a,b } {a} ∪ {b} {a} {b} ({a} ∪ {b})* {a} ∪ {b}* {a} + ∪ {b} a|b ab ( a|b )* a|b * a + |b a,b ab ε , a,b,ab,ba,abaab ,…. ε , a,b,bb,bbb,bbbb ,…. a,b,aa,aaa,aaaa ,…. ∑={ a,b,c,d } ({a}{b} ∪{c}{d})* ({a}{b} + ∪{c}* {d})* ( ab|cd )* (ab + |c*d)* ε , ab,cb,abcdcdab,cdcdcdab ,. ε , ab,d,abbbcccd,abdabd,abbbbdabd ,...

7. Ejemplo: Expresión Cadenas L=a*b* c + d + e cde,abcde,acde,bcde,aaabbccddde ,… L=(ab)*c(de) + cde,adcde,ababababcdedede,ababcdededede ,…. L=01|0 01,0 L=(01|0)* ε ,0,01,00101000101000,01010101,…… L=(ab)*|( cd )* ε , ab,cd,abababab …., cdcdcdcd …,…. L= a + b|c + d ab,cd,aab,aaab,aaa … b,ccd,cccd,ccc …d,….

8. Algebra de expresiones regulares. Si se extiende los conceptos de la teoría de conjunto a los lenguajes que son reconocidos por las expresiones regulares, se obtiene las siguientes propiedades: Axioma Descripción a|b = b|a | es conmutativo. a|( b|c )=( a|b )|c | es asociativo. (ab)c=a( bc ) La concatenación es asociativa a( b|c )= ab|ac ( a|b )c= ac|bc La concatenación distribuye sobre | ε r=r r ε =r ε es el elemento de identidad para la concatenación. r*=(r| ε ) + La relación entre * y ε r**=r* * Es idempotente

9. Ejemplos: Expresión regular redundante Expresión regular simplificada ε 1 1 ( abc ) ε abc aa * a + (ab)** (ab)* (001)*(001)* (001)* (001)(001)* (001) + (a| ε ) + |( bcd | ε ) + a*|( bcd )*

10. 2.3.- Aplicaciones en problemas reales.

11. Diseño de expresiones regulares. Para definir de manera rápida o directa un lenguaje, se recurre a un diagrama arbitrario que representa el patrón de comportamiento de un lenguaje; tal diagrama se conoce como diagrama sintáctico. Este diagrama, en este momento, sirve para definir un lenguaje de manera directa. Primitivas. Las primitivas pretende definir la técnica inicial para diseñar la expresión regular con relación al lenguaje propuesto por el diagrama sintáctico, sin embargo, esta definición es una recomendación. No existe ningún formalidad para realizar la conversión, literalmente el diseño de la expresión regular es “ a ojo de buen cubero “.

12. Diagramas. a b a b a a L= a|b Unión Concatenación L=ab Cerradura ( * ) Cerradura ( + ) L=a* L=a +

13. Ejemplo: L=(ab) + cd ( ecd )* L= abc *d( ed )* e a b c d d e a b c

14. Ejemplo: L=a( ba|ca )* L=a(( b|c )a)* L=a(( ba )*( ca )*)* L=a(b( db )* a|c ( ec )*a)* a b c b d e a c