Lenguaje de Operaciones

Anny Jimenez 13-1015

Aner Santana 13-1014

Las operaciones

• Las operaciones que se pueden utilizar para construir idiomas de otros idiomas.

• Recuerde: Un idioma es cualquier conjunto de cadenas.

• Palabra o cadena: es una secuencia de símbolos del alfabeto, es decir, s = a1a2...an, donde ai .

• Sea un alfabeto Σ. Una palabra sobre Σ es una secuencia finita de las letras de ese alfabeto.

• La secuencia vacía representa la palabra vacía y la anotamos con λ.

Ejemplos:

• sobre Σ5 ={a,b,c,d}:

• λ, a, b, c, d, abc, aab, dcba, ...

• sobre Σ1 ={0,...,9}:

• λ, 0, 0000, 010, 9980, ...

• sobre Σ3 ={(,)}

• λ, (, ), (), (()()), )())),

Por lo general se utilizan las primeras letras del alfabeto, a, b, c, d, e, para denotar símbolos del alfabeto y las últimas letras, s, t, u, v, w, x, y, z, para denotar palabras.

• Longitud de una palabra: es el número de

símbolos en s. Se denota por |s|.

•Palabra nula o vacía : es la palabra de longitud cero. Algunos autores utilizan para denotarla.

•Concatenación: si s = a1a2...an y t = b1b2...bn,

entonces

•st = a1a2...anb1b2...bn; s2 = ss; s3 = sss. La concatenación esasociativa, es decir, s(tu) = (st)u, pero no es conmutativa.

Concatenación de lenguajes

• L1L2 = {w | w = xy, x L1 y y L2}• Para un lenguaje L:

• L0 = {}

• L1 = L

• L2 = L L

• L3 = L L L

• ...

• L* = L0 L1 L2 L3 ... (Cerradura de Kleene)

• L+ = L1 L2 L3 ... = LL*

6

Ejemplo de concatenación

• X = {a, b, c}; Y = {abb, ba}• XY ={aabb, aba, babb, bba, cabb, cba}

• X0 = {}

• X1 = {a, b, c}

• X2 = XX = {aa, ab, ac, ba, bb, bc, ca, cb, cc}

• X3 = X2X = {aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc}

7

La operación ‘Kleene Star’

• La operación ‘Kleene Star’ tiene el mayor grado de precedencia,

• seguido de la concatenación y la unión.

• Por último, podemos decir que las expresiones regulares, al

• igual que las gramáticas, son una notación usada para especificar

• o definir un lenguaje

• Ejemplo: Sea S = {a,b}

1. La expresión regular (a|b) denota el lenguaje {a, b}

2. La ER (a|b)(a|b) denota el lenguaje {aa,ab,ba,bb}

3. La ER a* denota el lenguaje {, a, aa, aaa,...}

4. La ER (a|b)* denota el lenguaje de todos loas cadenas que

• contienen cero o mas instancias de una a o b, esto es,

• el conjunto de todas las cadenas de a’s y b’s.

Ejemplos de Cerradura de Kleene• L = {0, 11}• L0 = {}

• L1 = {0, 11}

• L2 = {00, 011, 110, 1111}

• L3 = {000, 0011, 0110, 01111, 1100, 11011, 11110, 111111}

• L4 = {0000, 00011, 00110, 001111, 01100, 011011, 011110, 0111111, 11000, 110011, 110110, 1101111, 111100, 1111011, 1111110, 11111111}

• L* son todas las que se pueden formar concatenando cualquier número de veces (excepto ) palabras de L. Las palabras pueden ser iguales o distintas.

• ¿Cuántos elementos tiene Ln}: 2n

• Independientemente del lenguaje, ¿Ln tiene siempre 2n

elementos?

9

• Las expresiones regulares se utilizan para abreviar la descripción de conjuntos regulares.

• El conjunto regular {a} es representado por a.

• Las operaciones de unión, concatenación y cerradura de Kleene son denotadas por +, yuxtaposición y *, respectivamente.

Definición recursiva de una expresión regular.Sea S un alfabeto.

• Las expresiones regulares sobre S se definen recursivamente de la siguiente manera:

• Base: , y a, para toda a S, son expresiones regulares sobre S.

• Paso recursivo: Si u y v son expresiones regulares sobre S, entonces las expresiones (u+v), (uv) y (u*) también lo son y representan a los conjuntos {u} {v}, {u}{v} y {u}*, respectivamente.

• Cerradura: u es una expresión regular sobre S sólo si puede ser obtenido a partir de los elementos base mediante un número finito de aplicaciones del paso recursivo.

Propiedades de cierre

• Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son lenguajes regulares los siguientes lenguajes también serán regulares:

• El complemento de L

• La clausura o estrella de Kleene L* de L

• El homomorfismo φ(L) de L

Propiedades de cierre

• La concatenación L'P de L y P

• La unión L ∪ P de L y P

• La intersección L ∩ P de L y P

• La diferencia L \ P de L y P

• El reverso LR de L