PDF de programación - Expresiones Regulares

Imágen de pdf Expresiones Regulares

Expresiones Regularesgráfica de visualizaciones

Publicado el 21 de Septiembre del 2020
219 visualizaciones desde el 21 de Septiembre del 2020
563,4 KB
52 paginas
Creado hace 4a (10/05/2016)
Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Expresiones Regulares

INAOE

(INAOE)

1 / 52

Contenido

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

1 Expresiones Regulares

2 Operadores y Operandos

3 Equivalencia de Lenguajes de FA y Lenguajes RE

4 Leyes Algebraicas de las Expresiones Regulares

(INAOE)

2 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Expresiones Regulares

Expresiones Regulares

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

(INAOE)

3 / 52

Expresiones Regulares

Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

• Ejemplos de sus usos

expresión regular para describir patrones

• Comandos de búsqueda, e.g., grep de UNIX
• Sistemas de formateo de texto: Usan notación de tipo
• Convierte la expresión regular a un DFA o un NFA y
• 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), como while, números, signos (+,−, <, etc.)

simula el autómata en el archivo de búsqueda

• Produce un DFA que reconoce el token

(INAOE)

4 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Expresiones Regulares

Expresiones Regulares

• 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 de 1’s o un 1 seguido de cualquier cantidad de
0’s.

• Operaciones de los lenguajes:

1 Unión: Si L y M son dos lenguajes, su unión se denota

2 Concatenación: La concatenación es: LM o L.M (e.g.,

3 Cerradura (o cerradura de Kleene): Si L es un lenguaje

por L ∪ M (e.g., L = {11, 00}, M = {0, 1},
LcuoM = {0, 1, 00, 11})
LM = {110, 111, 000, 001} )
su cerradura se denota por: L∗
(L0 = {}, L1 = L, L2 = LL. Si
L = {0, 11}, L2 = {00, 011, 110, 1111})

(INAOE)

5 / 52

Operadores y Operandos

Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

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

1 Las constantes  y ∅ son expresiones regulares que

representan a los lenguaje L() = {} y L(∅) = ∅
respectivamente

2 Si a es un símbolo, entonces es una expresión regular

que representan al lenguaje: L(a) = {a}

(INAOE)

6 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Operadores y Operandos

Operandos

1 Si E y F son expresiones regulares, entonces E + F

también lo es denotando la unión de L(E) y L(F ).
L(E + F ) = L(E) ∪ L(F ).

2 Si E y F son expresiones regulares, entonces EF

también lo es denotando la concatenación de L(E) y
L(F ). L(EF ) = L(E)L(F ).

3 Si E es una expresión regular, entonces E∗ también lo

es y denota la cerradura de L(E). Osea
L(E∗) = (L(E))∗

4 Si E es una expresión regular, entonces (E) también lo

es. Formalmente: L((E)) = L(E).

(INAOE)

7 / 52

Operadores y Operandos

Precedencia

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

1 El asterisco de la cerradura tiene la mayor precedencia
2 Concatenación sigue en precedencia a la cerradura, el

operador “dot”. Concatenación es asociativa y se
sugiere agrupar desde la izquierda (i.e. 012 se agrupa
(01)2).

3 La unión (operador +) tiene la siguiente precedencia,

también es asociativa.

4 Los paréntesis pueden ser utilizados para alterar el

agrupamiento

(INAOE)

8 / 52

Operadores y Operandos

Ejemplos

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

• L(001) = 001.
• L(0 + 10∗) = {0, 1, 10, 100, 1000, . . .}.
• L((0(0 + 1))∗) = el conjunto de cadenas de 0’s y 1’s, de

1 (01)∗ + (10)∗ + 0(10)∗ + 1(01)∗ (opción 1)
2 ( + 1)(01)∗( + 0) (opción 2)

longitud par, de tal manera que cada posición impar
tenga un 0.

• Expresión regular de cadenas que alterna 0’s y 1’s:

(INAOE)

9 / 52

Operadores y Operandos

Ejemplos

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

1 Encuentra la expresión regular para el conjunto de

cadenas sobre el alfabeto {a, b, c} que tiene al menos
una a y al menos una b

2 Encuentra la expresión regular para el conjunto de

cadenas de 0’s y 1’s tal que cada par de 0’s adyacentes
aparece antes de cualquier par de 1’s adyacentes

(INAOE)

10 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Operadores y Operandos

Soluciones

1 c∗a(a + c)∗b(a + b + c)∗ + c∗b(b + c)∗a(a + b + c)∗

Osea, cuando la primera a esta antes que la primera b
o cuando la primera b está antes de la primera a

2 (10 + 0)∗( + 1)(01 + 1)∗( + 1)

(10 + 0)∗( + 1) es el conjunto de cadenas que no
tienen dos 1’s adyacentes. La segunda parte es el
conjunto de cadenas que no tienen dos 0’s adyacentes.
De hecho  + 1 lo podríamos eliminar porque se puede
obtener el 1 de lo que sigue, por lo que podemos
simplificarlo a: (10 + 0)∗(01 + 1)∗( + 1)

(INAOE)

11 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Equivalencia de Lenguajes de FA y Lenguajes RE

Equivalencia de Lenguajes de FA y

Lenguajes RE

• Se mostrará que un NFA con transiciones- puede

aceptar el lenguaje de una RE.

• Después, se mostrará que un RE puede describir el
lenguaje de un DFA (la misma construcción funciona
para un NFA).

• Los lenguajes aceptados por DFA, NFA, -NFA, RE son

llamados lenguajes regulares.

(INAOE)

12 / 52

Equivalencia de Lenguajes de FA y Lenguajes RE

De DFA’s a Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Teorema 3.4: Si L = L(A) para algún DFA A, entonces
existe una expresión regular R tal que L = L(R).
Prueba: Suponiendo que A tiene estados {1, 2, . . . , n}, n
finito. Tratemos de construir una colección de RE que
describan progresivamente conjuntos de rutas del diagrama
de transiciones de A

• R(k)

ij es el nombre de la RE cuyo lenguaje es el
conjunto de cadenas w.

• w es la etiqueta de la ruta del estado i al estado j de A.

Esta ruta no tiene estado intermedio mayor a k. Los
estados inicial y terminal no son intermedios, i y/o j
pueden ser igual o menores que k

(INAOE)

13 / 52

Equivalencia de Lenguajes de FA y Lenguajes RE

De DFA’s a Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

• Para construir R(k)
ij
k = 0 hasta k = n

se utiliza una definición inductiva de

• BASE: k = 0, implica que no hay estados intermedios.
Sólo dos clases de rutas cumplen con esta condición:

1 Un arco del nodo (estado) i al nodo j
2 Una ruta de longitud 0 con un solo nodo i

• Si i = j, solo el caso 1 es posible.

(INAOE)

14 / 52

Equivalencia de Lenguajes de FA y Lenguajes RE

De DFA’s a Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Examinar el DFA A y encontrar los símbolos de entrada a tal
que hay una transición del estado i al estado j con el
símbolo a

ij = ∅.
• Si no hay símbolo a, entonces R(0)
• Si hay sólo un símbolo a, entonces R(0)
ij = a.
• Si hay varios símbolos a1, a2, . . . , ak, entonces

R(0)
ij = a1 + a2 + . . . + ak.

(INAOE)

15 / 52

Equivalencia de Lenguajes de FA y Lenguajes RE

De DFA’s a Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Si i = j, sólo se permiten rutas de longitud 0 y ciclos del
estado i a él mismo.

• La ruta de longitud 0 se representa con 
ij = ∅
• Si no hay símbolo a, entonces R(0)
• Si hay sólo un símbolo a, entonces R(0)
ij =  + a.
• Si hay varios símbolos a1, a2, . . . , ak, entonces

R(0)
ij =  + a1 + a2 + . . . + ak.

(INAOE)

16 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Equivalencia de Lenguajes de FA y Lenguajes RE

De DFA’s a Expresiones Regulares

INDUCCI ÓN: Suponemos que hay una ruta del estado i al
estado j que no pasa por ningún estado mayor que k.
Se consideran 2 casos.

1 La ruta no pasa por el estado k: La etiqueta de la ruta

está en el lenguaje R(k−1)

.

ij

2 La ruta pasa por el estado k al menos una vez:

• Se divide la ruta en varias partes, una división por cada
• Primero del estado i al estado k, después, varios pasos

vez que se pasa por el estado k

del estado k a sí mismo, finalmente, del estado k al
estado j.

Las etiquetas de estas rutas se r
  • Links de descarga
http://lwp-l.com/pdf18238

Comentarios de: Expresiones Regulares (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad