Unidad 2 Lenguajes y Automatas 1 - Expresiones Regulares.
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 Σ, 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.
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 la operación de concatenarlo consigo mismo i veces.
Li= LLL ....L
|------------|
i
|------------|
i
Clausura positiva de un lenguaje: Se define la clausura
positiva de un lenguaje L:
∞
L + = U L i
i=1
∞
L + = U L i
i=1
Lenguaje obtenido 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
∞
L* = U Li
i=0
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.
2.3 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.
gracias por la info :3
ResponderBorrarmuy rico y todo pero no tiene referencias
ResponderBorrar