Definición Formal de Una ER
Definición Formal de Una ER
Definición Formal de Una ER
Ofrecen algo que los autómatas no: Manera declarativa de expresar las cadenas que queremos
aceptar.
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), (α).
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.
Los analizadores léxicos son parte de un compilador. Dividen el programa fuente en unidades
lógicas (tokens) divide el programa fuente en unidades.
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.
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}.
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}
Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles excepto Lº. Si L no
contiene la palabra vacía, la clausura positiva tampoco
Lenguaje obtenido uniendo el lenguaje con todas 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 de r y s y lo podemos definir: L( r | s ) = L( r ) U L( s ). Esta operación
se puede extender a más de dos ER.
Concatenación: Se indica con la yuxtaposición de las ER. Si r y s son ER, entonces rs es una ER que
define a cualquier cadena que concuerde con la concatenación de r y s , esta operación la
podemos definir: L(rs) = L(r)L(s).Esta operación se puede extender a más de dos ER.
Repetición o Cerradura: También se conoce con el nombre de cerradura de Kleene. Se indica con
el operador *. Si r es una ER, entonces r* es una ER que define a las cadenas de caracteres
representadas por la concatenación repetida de r en n veces, o sea que lo podemos definir como:
L(r*) = L(r)*o también lo podemos definir como la unión infinita de conjuntos r :r* n = r 0 r 1 r 2...r
n.
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.