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

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