Download - 02 - Expresiones Regulares (1)
-
8/18/2019 02 - Expresiones Regulares (1)
1/14
6/3/2009
1
Instituto Politécnico Nacionalnstituto Politécnico Nacional
Centro de Investigación en ComputaciónCentro de Investigación en Computación
CURSO PROPEDÉUTICO:
L
ENGUAJES FORMALES
, G
RAMÁTICAS Y
A
UTÓMATASENGUAJES FORMALES
, G
RAMÁTICAS Y
A
UTÓMATAS
CURSO PROPEDÉUTICO:
MATEMÁTICA DISCRETA
Sesión 2
Expresiones Regularesxpresiones Regulares
Recordatorio
sesión anterior
-
8/18/2019 02 - Expresiones Regulares (1)
2/14
6/3/2009
2
Conceptos...Conceptos...
Sintaxis, Semántica y Pragmática
Relevancia de estudiar el procesamiento
simbólico
Alfabeto
Cadena o Palabra
33
Operaciones con Lenguajes
Cerradura y Cerradura Positiva
EjemploEjemplo
Los numerales romanos son cadenas sobre unalfabeto de ocho símbolos:
R I V X L C D M
Algunas cadenas correctas en el lenguaje delos numerales romanos:
XXXVII XL XCIX
44
MCMXCIX MCM CIV
IV MCDXLIV MMIX
Observe que no cualquier cadena sobre R
esparte del lenguaje.
-
8/18/2019 02 - Expresiones Regulares (1)
3/14
6/3/2009
3
…sobre la Cerradura…sobre la Cerradura
Si es un alfabeto, es el conjunto detodas las posibles cadenas sobre
* L
Entonces, si L es un lenguaje sobre
,
forzosamente
es el lenguaje más grande posible sobre
55
El operador de cerradura también aplicapara lenguajes
Lenguajes
Regulares
-
8/18/2019 02 - Expresiones Regulares (1)
4/14
6/3/2009
4
PresentaciónPresentación
Se pueden construir usando las operacionesde: Unión
, Producto
y erradura
.
Sea un alfabeto,
DEFINICIÓN INDUCTIVA
Caso base: , }{ s y son Lenguajes RegularesPara todo símbolo s
Inducción: Si L M
son dos Len ua es Re ulares
77
Cerradura:
Los lenguajes regulares son única y exclusivamenteaquellos que satisfacen los pasos anteriores.
*, L M L M y L
L M
entonces también lo son:
EjemploEjemplo
,a b Sea
os s gu entes son a gunos engua es regu ares:
Paso base:
Paso de inducción:
,a b a b
b a b ba bb
88
a b
* , , , ,...b b bb bbb
, , , , ,ba bb a b baa bab bba bbb
-
8/18/2019 02 - Expresiones Regulares (1)
5/14
6/3/2009
5
CorolarioCorolario
Para saber si un lenguaje es regular o no,basta factorizarlo usando unión, producto o
.
, , , ,..., ,...n L a ab abb abbb ab
,a b
Sea
un lenguaje sobre
99
¿es L un lenguajeregular?
SoluciónSolución
,a b
, , , ,..., ,...n L a ab abb abbb ab
, , , ,...a b bb bbb
*a b
1010
Lo cual, por definición, es Regular !!!
-
8/18/2019 02 - Expresiones Regulares (1)
6/14
6/3/2009
6
Otro ejemploOtro ejemplo
,0,1,00,11,...,0 ,1 ,...n n L
Sea
,
,0,1,00,11,...,0 1 ,...n n L
, 0, 00,..., 0 ,... ,1,11,...,1 ,...n n * *
1111
0 1
Lo cual, por definición, es Regular !!!
Expresiones
Regulares
-
8/18/2019 02 - Expresiones Regulares (1)
7/14
6/3/2009
7
¿Qué son y para qué sirven?¿Qué son y para qué sirven?
Se trata de expresiones algebraicas de la formaque presentan
las cadenas de un lenguajeregular
Operación con
lenguajes Expresión regular
L M
* L
L M L M
LM
* L
Operación Prioridad Orden
* (calcular
1313
L
L al inicio)
. Media
+ Baja (calcular
al final)
Evidentemente…Evidentemente…
DEFINICIÓN INDUCTIVA
Caso base
xpresiones Regulares
aso base:
, xpresiones Regulares
para todo símbolo s
Inducción:
*
Si R
y S
son dos expresiones regulares,entonces también lo son:
1414
Cerradura:
Las expresiones regulares son única y exclusivamente aquellos que satisfacen los pasosanteriores.
,
-
8/18/2019 02 - Expresiones Regulares (1)
8/14
6/3/2009
8
Expresión…Expresión…
Las unidades atómicas de las expresionesregulares son los símbolos del alfabeto.
,00,11,0011,0000,1111,1100,... L
*
00 11
Se representa mediante la expresiónregular:
1515
“Cero o más ocurrencias (por la cerradura
), ya sea de doble cero, o bien (por la unión),de doble uno"
Más ejemplos…Más ejemplos…
0,1 Si , entonces
*0 1es e uivalente a*
*
1 10 y todas las cadenas que comienzan
en 1 y jamás presentan un doble 0.
*0 1 011 odas las cadenas que terminan en
1616
011.
* *
0 1 00 0 1 Cadenas con, al menos un doble 0.
-
8/18/2019 02 - Expresiones Regulares (1)
9/14
6/3/2009
9
CorrespondenciaCorrespondencia
Al lenguaje descrito por una expresión
regular R
se le denota R)
.
s
P Q
s
P Q
1717
PQ
*P *P
P Q
Al final…Al final…
Toda expresión regular denota o especificaun lenguaje regular,
Todo lenguaje regular puede ser denotadopor una expresión regular.
Para encontrar el lenguaje que denota una
1818
expresi n regu ar se pue e proce er“desarrollando” los lenguajes respectivos.
-
8/18/2019 02 - Expresiones Regulares (1)
10/14
6/3/2009
10
EjemploEjemplo
¿ Qué lenguaje denota la expresión ?*a bcSolución: se puede proceder de la siguientemanera:
* *a bc a bc
*a b c
*a b c
*a b c , ,a b c
1919
, , , .,...a b c cc ccc , , , .,...a b bc bcc bccc
, , , , ,...a b bc bcc bccc
EquivalenciaEquivalencia
Dos o más expresiones regulares puedenser equivalentes si denotan exactamentee m smo engua e
Considere, por ejemplo, las expresiones:
a b y b a
2020
,a b a b a b
,b a b a a b
-
8/18/2019 02 - Expresiones Regulares (1)
11/14
6/3/2009
11
Sin embargo…Sin embargo…
¡ Cuidado ! Es necesario recordarque la concatenación, y por tanto elpro uc o, no son conmu a vos, asque:
Considere ahora las expresiones:
ab y ba
2121
aab a b b
bba b a a
Algunos ejercicios
sencillos
-
8/18/2019 02 - Expresiones Regulares (1)
12/14
6/3/2009
12
Lenguaje de las expresionesLenguaje de las expresiones
Encuentre el lenguaje denotado por las
si uientes ex resiones re ulares sobre el
alfabeto
*( ) xx yx
, x y
* * xx yy
2323
*( ) xyx yxx *( ) xy yy xy
Reflexión
final
-
8/18/2019 02 - Expresiones Regulares (1)
13/14
6/3/2009
13
Es decir…Es decir…
¡¡ Todo lenguaje finito es regular !!
cadenas que conforman el lenguaje.
, , , L xx yy zz ww
xx yy zz ww
2525
Los lenguajes infinitos pueden ser regulares, obien, no serlo.
n n L a b n N
Y…¿si no es regular?Y…¿si no es regular?
Las expresiones regulares sólo son útilesara denotar len ua es re ulares, ero…
Si un lenguaje no es regular… ¿cómo lodenotamos?
2626
cualquier tipo de lenguaje formal…
Las GRAMÁTICAS
-
8/18/2019 02 - Expresiones Regulares (1)
14/14
6/3/2009
14
Instituto Politécnico Nacionalnstituto Politécnico Nacional
Centro de Investigación en ComputaciónCentro de Investigación en Computación
L
ENGUAJES FORMALES
, G
RAMÁTICAS Y
A
UTÓMATASENGUAJES FORMALES
, G
RAMÁTICAS Y
A
UTÓMATAS
Símbolos, Cadenas y Lenguajesímbolos, Cadenas y Lenguajes