Expresiones R

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 queremosaceptar.
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 deUNIX.
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 programafuente 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: Laconcatenació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 elmismo 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 Φ = Φ
Potencia de un lenguaje: Se define la potencia i-ésima de un lenguaje a laoperación de concatenarlo consigo mismo i veces.
Li= LLL ....L
|------------|
i
Clausura positiva de un lenguaje: Se define la clausura positiva de un lenguaje L:
∞
L + = U L i
i=1
Lenguajeobtenido uniendo el lenguaje con todas sus potencias posibles excepto Lº. Si L no contiene la palabra vacía, la clausura positiva tampoco
Cierre o Clausura de un lenguaje: Se define el cierre o clausura de un lenguaje L como :
∞
L* = U Li
i=0

Lenguaje obtenido uniendo el lenguaje contodas sus potencias posibles, incluso Lº. Todas las clausuras contienen la palabra vacía.
Existen tres operaciones básicas que se pueden realizar sobre las ER:
Selección de alternativas : Se indica con el operador |(barra vertical). Si r y s son ER, entonces r | s es una ER que define a cualquier cadena que concuerde con una r o una s, también se dice que r | s , es la unión de los lenguajes...