PDF de programación - Expresiones regulares, gramáticas regulares

Imágen de pdf Expresiones regulares, gramáticas regulares

Expresiones regulares, gramáticas regularesgráfica de visualizaciones

Publicado el 14 de Agosto del 2020
315 visualizaciones desde el 14 de Agosto del 2020
345,8 KB
28 paginas
Creado hace 5a (26/02/2015)
Expresiones regulares,
gramáticas regulares

Los LR en la jerarquía de Chomsky

 La clasificación de lenguajes en clases de

lenguajes se debe a N. Chomsky, quien
propuso una jerarquía de lenguajes, donde
las clases más complejas incluyen a las más
simples.

 Los “lenguajes regulares” es la clase más

pequeña, e incluye a los lenguajes más
simples. Por ejemplo, el conjunto de todos
los números binarios.

 Los “lenguajes libres de contesto” incluyen a

los LR. Por ejemplo, la mayoría de los
lenguajes de programación.

 Los “lenguajes recursivamente enumerables”

que incluyen a los dos anteriores.

Lenguajes regulares

 Los LR se llaman así porque sus palabras contienen

“regularidades” o repeticiones de los mismos componentes, por
ejemplo:
 L1={ab, abab, ababab, abababab,…}

 Las palabras de L1 son simplemente repeticiones de “ab”

cualquier número de veces. La “regularidad” consiste en que las
palabras contienen “ab” algún número de veces.

 Otro ejemplo:

 L2={abc, cc, abab, abccc, ababc, …}
 La regularidad consiste en que sus palabras inician con

repeticiones de “ab” seguidas de repeticiones de “c”.

 Los lenguajes finitos son también regulares por definición.

Ejemplo: L3= {el, coche, verde}

 La combinación de lenguajes regulares (unión o concatenación),

también producen un lenguaje regular.

Definición de Lenguajes Regulares

 Un lenguaje L es regular si y sólo si se
cumple al menos una de las siguientes
condiciones:
 L es finito,

 L es la unión o la concatenación de otros
lenguajes regulares R1 y R2, L=R1υ R2 o
L=R1R2 respectivamente.

 L es la cerradura de Kleene de algún lenguaje

regular, L=R*.

Ejemplo

 Sea el lenguaje L de palabras formadas por a y b
pero que empiezan con a, como aab, ab, a, abaa,
etc. Probar que este lenguaje es regular, y dar una
expresión de conjuntos que lo represente.
 El alfabeto es ∑={a, b}. El lenguaje L puede ser visto como
la concatenación de una a con cadenas cualesquiera de a
y b; ahora bien, éstas últimas son los elementos de {a, b}*,
mientras que el lenguaje que sólo contiene la palabra a es
{a}. Ambos lenguajes son regulares. Es decir, {a} es finito,
por lo tanto regular, mientras que {a,b}* es la cerradura de
{a,b}, que es regular por ser finito. Entonces la
concatenación es {a}{a,b}*, es regular.

 Sea ∑ un alfabeto. La expresión regular sobre ∑ y

los conjuntos que ellas denotan son definidos
recursivamente como sigue:
 Ø es una expresión regular y denota el conjunto vacio.

 ɛ es una expresión regular y denota el conjunto {ɛ}.

 Para cada a en ∑, a es una expresión regular y denota el

conjunto {a}.

 Si r y s son expresiones regulares denotando el lenguaje R

y S, respectivamente, entonces (r + s), (rs), y (r*) son
expresiones regulares que denotan los conjuntos RυS, RS,
y R*, respectivamente.

Ejemplo

 Sea L1={10,1} y L2={011,11}. Entonces

 L1L2={10011, 1011, 111}

 {10, 11}*= { ɛ, 10, 11, 1010, 1011, 1110, 1111, …}



 Observación: L+ contiene a ɛ si y solo si L lo tiene.

 En la escritura de expresiones regulares, se pueden

omitir parentesis si asumimos que * tiene más alta
precedencia que la concatenación o +, y que la
concatenación tiene más alta precedencia que +-



Definición

 Sea ∑ un alfabeto. Las expresiones regulares (ER)

definidas sobre ∑ y los conjuntos regulares que
denotan se definen recursivamente:



 Donde r, s son ERs que denotan a los conjuntos R,
S respectivamente. Nótese que los paréntesis sólo
son agrupadores.

Ejemplo

 Sea la ER (0 + 1)*. Analizando detalladamente

(obteniendo los correspondientes conjuntos para
cada subexpresión):
 0 es la ER que denota al conjunto {0},

 1 es la ER que denota al conjunto {1},

 (0 + 1) = {0} υ {1} = {0,1}

 Entonces:

 {0,1}* ={ɛ, 0, 1, 01, 10 11, 00, 000, 001, … }

 Representa el conjunto de todas las posibles cadenas que se

pueden formar con ‘0’ y ‘1’.



Jerarquía de prioridad y asociatividad

 La cerradura * asocia por la izquierda y tiene

la mayor prioridad, a continuación la
concatenación (asocia por la derecha) y
finalmente el operador de alternativa + ue
también asocia por la derecha.

 Ejemplo: 0 + 1b* + a1* es igual a

 (0 + ((1(b*)) + (a(1*))))

Ejemplos

 Sea el alfabeto ∑={a,b,c},



 La ER denota al conjunto de todas las cadenas que

comienzan con ‘a’ o ‘b’ seguidas de cualquier
número de ‘c’s incluyendo ɛ.

Ejemplo



Ejemplo



 Son todas las cadenas pares de 0’s ó cadenas

impares de 1’s.

Ejercicio

 Determine el conjunto de “(((a + b))*a)”

Solución

 {a,b}*{a} es el lenguaje sobre {a,b} de las

palabras que terminan en a.

Ejercicio

 Dada la expresión regular E=0*10*, obtenga

el lenguaje que representa

Solución

 {0}*{1}{0}* = {0n10m | n,m >= 0}

Equivalencia entre AF y ER

 Teorema. Sea r una expresión regular que
denota al conjunto R. Existe un AFND-ɛ M
que acepta al lenguaje que denota r: L(M)=R.

 Demostración: aplicaremos inducción sobre
el número de operadores involucrados en la
ER r, el AFND-ɛ tendrá un estado final y
ninguna transición fuera de ese estado final,
tal que L(M)=L(r).

 Caso base: el número de operadores es 0 (no hay

alguno), la ER r corresponde a alguna de Ø, ɛ, a
como se muestra en la Figura para los casos base.



 Paso inductivo: Se asume que la afirmación es

verdadera para toda ER con menos de i
operadores, para i>=1. Sea r con i operadores:



fo

o



02





Por lo tanto: L(M)=L(M1)*

f0

Ejemplo

 Construir un AFN-e para la expresión regular

01* +1. Esta expresión es: (0(1*))+1, así
 r1= 01* y r2=1. El autómata para r2 es:



 Ahora, r1=r3r4, donde r3=0 y r4=1*. El autómata

para r3 es



 R4 es r5*, donde r5 es 1. Un AFN para r5 es



Ejemplo

 Construir un AFND-Ɛ para la ER ab*+a.

Ejercicio

 Obtener el AF asociado a (10+0)*011

Propuesta de solución

 (10+0)*011
  • Links de descarga
http://lwp-l.com/pdf18070

Comentarios de: Expresiones regulares, gramáticas 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