PDF de programación - Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Expresiones Regulares

6 de mayo de 2015

()

6 de mayo de 2015

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

()

6 de mayo de 2015

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

()

6 de mayo de 2015

3 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Expresiones Regulares

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.

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

Dividen el programa fuente en unidades lógicas
(tokens). Tokens como while, números, signos (+,−, <,
etc.)

• Produce un DFA que reconoce el token

()

6 de mayo de 2015

4 / 52

Expresiones Regulares

Expresiones Regulares

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
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 seguida 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

por L ∪ M

2 Concatenación: La concatenación es: LM o L.M
3 Cerradura (o cerradura de Kleene): Si L es un lenguaje

su cerradura se denota por: L∗.

()

6 de mayo de 2015

5 / 52

Expresiones
Regulares

Operadores y
Operandos

Equivalencia
de Lenguajes
de FA y
Lenguajes RE

Leyes
Algebraicas
de las
Expresiones
Regulares

Operadores y Operandos

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}

()

6 de mayo de 2015

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

()

6 de mayo de 2015

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

()

6 de mayo de 2015

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:

()

6 de mayo de 2015

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

()

6 de mayo de 2015

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)

()

6 de mayo de 2015

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.

()

6 de mayo de 2015

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

()

6 de mayo de 2015

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.

()

6 de mayo de 2015

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.

()

6 de mayo de 2015

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.

()

6 de mayo de 2015

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 cada que
• Primero del estado i al estado k, después, varios pasos

se pasa por el estado k

del estado k a sí mis