Unidad 2 Automatas finitos

Expresiones Regulares (ER)

Aplicaciones en problemas reales Una de las principales aplicaciones de los hermanos Deitel, son las expresiones regulares que facilitan la construcción de un compilador. A menudo se utiliza una expresión regular larga y compleja para validar la sintaxis de un programa. Si el código del programa no concuerda con la expresión regular, el compilador sabe que hay un error de sintaxis dentro del código. Generalmente convierten la expresión regular a un autómata finito no determinista y después construyen el autómata finito determinista. Otra aplicación del mismo libro es en los editores de texto. También encontramos a las expresiones regulares en la biología molecular. También hay esfuerzos importantes para tratar de representar cadenas como generadas por expresiones regulares o por lenguajes regulares.

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 Σ.

operaciones *Unión o Alternativa*Concatenación*Potencia de un lenguaje*Clausura positiva de un lenguaje*Cierre o Clausura de un lenguaje*Selección de alternativas *Concatenación*Repetición o Cerradura 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. La concatenación de lenguajes con el lenguaje vació es ΦL = L Φ = Φ

DEPARTAMENTO DE INGENIERIA EN SISTEMAS COMP. ING: MANUEL HERNANDEZ HERNANDEZ LENGUAJES Y AUTOMATAS 1 ELIZABETH MARTIN DEL ANGEL S/6-A