EXPRESIONES REGULARES Y SUS OPERACIONES

            [pic 1]

    INSTITUTO TECNOLOGICO SUPERIOR DE JESUS CARRANZA

    [pic 2][pic 3][pic 4][pic 5]

DEPARTAMENTO DE INGENIERÍA

EN SISTEMAS COMPUTACIONALES

[pic 6]

ASIGNATURA

[pic 7]

• INVESTIGAR LAS EXPRESIONES REGULARES Y SUS OPERACIONES.

PRESENTA

                         ROSA ISELA ZACARIAS GONZALEZ

DOCENTE:

ING.AMADO LOPEZ HILARIO

JESUS CARRANZA VERACRUZ                         FEBRERO 2017

INDICE

INTRODUCCION        3

UNIDAD 2 - EXPRESIONES REGULARES.        4

2.1. DEFINICIÓN FORMAL DE UNA ER.        4

Ejemplos de usos.        4

2.2. OPERACIONES        5

Unión o Alternativa:        5

Concatenación:        5

Potencia de un lenguaje:        5

Clausura positiva de un lenguaje:        5

Cierre o Clausura de un lenguaje:        5

Repetición o Cerradura:        6

2.3 APLICACIONES EN PROBLEMAS REALES.        6

CONCLUCION        6

BIBLIOGRAFIA        7

INTRODUCCION

Las expresiones regulares se utilizan para hacer búsquedas contextuales y modificaciones sobre textos. A pesar de que las expresiones regulares estén muy extendidas por el mundo de Unix, no existe un lenguaje estándar de expresiones regulares. Más bien se puede hablar de diferentes dialectos. Perl se puede calificar como el lenguaje con la sintaxis de expresiones regulares más desarrollado.

UNIDAD 2 - EXPRESIONES REGULARES.

2.1. DEFINICIÓN FORMAL DE UNA ER.

Es un equivalente algebraico para un autómata.

• Utilizado en muchos lugares como un lenguaje para describir patrones en texto que son sencillos pero muy útiles.
• Pueden definir exactamente los mismos lenguajes que los autómatas pueden describir: Lenguajes regulares.
• Ofrecen algo que los autómatas no: Manera declarativa de expresar las cadenas que queremos aceptar.

Dado un alfabeto Dado un alfabeto Σ, una , expresión regular sobre expresión regular sobre Σ se define de forma recursiva:

• ER primitivas: Φ, λ, {a | a ЄЄЄ Σ Є}
• Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α).
• No existen otras reglas para la construcción de ER sobre Σ.

Ejemplos de usos.

• Comandos de búsqueda, e.g., grep de UNIX.
• sistema de formato de texto: Usan notación de tipo expresión regular para describir patrones.
• Convierte la expresión regular a un DFA o un NFA y simula el autómata en el archivo de búsqueda.
• Generadores de analizadores - Léxicos. Como Lex o Flex.
• Los analizadores léxicos son parte de un compilador. Dividen el programa fuente en unidades lógicas (tokens) divide el programa fuente en unidades.
• Produce un DFA que reconoce el token.

Las expresiones regulares denotan lenguajes.

Por ejemplo, la expresión regular: 01* + 10* denota todas las cadenas que son o un 0 seguido de cualquier cantidad 1's o un 1 seguida de cualquier cantidad de 0's.

Operaciones de los lenguajes:

• Unión: Si L y M  son dos lenguajes, su unión se denota por L U M.
• Concatenación: La concatenación es: LM o L.M.
• Cerradura (o cerradura de Kleene): Si L es un lenguaje su cerradura se denota por L *.

Si E es una expresión regular, entonces L(E) denota el lenguaje que define E. Las expresiones se construyen de la manera siguiente:

• Las contantes  y  son expresiones regulares que representan a los lenguajes L (Q) = {Q} y L (Φ) L = Φ respectivamente.
• Si a es un símbolo, entonces es una expresión regular que representan al lenguaje: L (a) = {a}.

2.2. OPERACIONES

Unión o Alternativa: Consideremos dos lenguajes diferentes definidos sobre el mismo alfabeto L1 ⊂ W(∑) y L2 ⊂ W(∑). Se denomina unión de ambos lenguajes al lenguaje formado por las palabras de ambos lenguajes:

• L1 U L2={ x | x ∈ L1 ó x ∈ L2}

Concatenación: Consideremos dos lenguajes definidos sobre el mismo alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el lenguaje L1 L2= { xy / x ∈ L1 y x ∈ L2} Las palabras de este lenguaje estarán formadas al concatenar cada una palabra del primero de los lenguajes con otra del segundo.

...