Lenguajes Formales y Gramáticas

Programación II

Margarita Álvarez

Introducción 



Teoría de la computabilidad: establece las limitaciones de las computadoras generalmente indicando la clase de problemas que pueden ser resueltos por computadoras. Para lo cual se necesita de modelos matemáticos precisos y un algoritmo para su solución. El modelo que casi siempre se usa es la Máquina de Turing.

La teoría de lenguajes formales y de autómatas pertenece a la teoría de la computabilidad.

Lenguaje Un lenguaje puede ser imaginado como un conjunto de sentencias con estructura bien definida y por lo general con significado. Sintaxis: define que líneas de caracteres son válidas. pq pq

fórmula proposicional válida fórmula proposicional no válida

Semántica: define el significado de la construcción del lenguaje. Asigna un significado o interpretación a los símbolos. pq

significa la disyunción de las proposiciones p y q

Definición de lenguajes Se usa cierto lenguaje L1 , para definir a otro lenguaje L2. El lenguaje L1 se denomina metalenguaje y L2 , lenguaje objeto. Los símbolos de L1 y L2 se

denominan

símbolos no terminales y símbolos terminales,

respectivamente. Ejemplo L1 = { x + y | y + x } se considera un lenguaje sobre el alfabeto x, y, +. Elementos del lenguaje: símbolos x, y, + Elementos del metalenguaje: símbolos {, }, |

Definición de lenguajes

Ejemplo

L2 = { xm + yn / m  1, n  1 } En el metalenguaje usado para especificar L2 los símbolos de potencia m y n significan que un número arbitrario de símbolos x y y aparecen en las hileras del lenguaje. Ya que m puede diferir de n, los números de las x en una hilera pueden diferir del número de las y. El símbolo / se usa en lugar de la palabra "donde" y las limitaciones de m y n que le siguen especifican que al menos una x y una y aparecerán en cualquier hilera válida.

Conceptos Básicos 

Símbolo: es simplemente una representación distinguible de cualquier información.  Es un elemento atómico e indivisible.  Ejemplos: w, 9, #, etc.

• Alfabeto o Vocabulario: es un conjunto finito y no vacío de símbolos arbitrarios (símbolos terminales). V = {a1 , a2 , ... , an } • Ejemplos: Alfabeto español V = {a, b, c, . . . , z} Alfabeto de máquina V = {0, 1} Alfabeto griego V = {, , . . . , }

Conceptos Básicos - Hilera 

Es cualquier string de longitud finita compuesto por símbolos sobre el vocabulario. Es un conjunto finito de símbolos yuxtapuestos. Ejemplo V = {a, b}

x= a y = b 

Longitud de una hilera: es la cantidad de símbolos que componen esa hilera. Ejemplo  Notación: |w| para una hilera w.

x = perro  |x| = 5 x = abba  |x| = 4



Hilera o palabra vacía: es la cadena de longitud cero.  Notación:  o 

Operaciones con Hileras Concatenación

 

Sea x= a1 a2 ... an y =b1b2 ... bm x.y = a1 a2 ... an b1b2 ... bm La concatenación:

Es asociativa: x(yz) = (xy)z No conmutativa: xy ≠ yx Posee elemento neutro:  x=x=x x  y = xy Longitud de concatenación |xy| = |x|+|y| Es una operación cerrada  x,y  V*: x . y  V*

Ejemplo x= abb y = bac xy = abbbac

Ejemplo x= ab y = bc z=de ab(bcde) = (abbc)de

Ejemplo x= abb y = bc abbbc ≠ bcabb

Operaciones con Hileras 

Potencia de una palabra (Concatenación iterativa)

Se llama potencia n-ésima de una palabra, a la operación que consiste en concatenar la palabra consigo misma n veces. Dada una palabra w  V*, se define inductivamente wn, como:

 wn = w.wn-1

si n = 0 si n > 0 Ejemplo

 Es necesario usar paréntesis cuando sea necesario.

Ejemplo (ab)3 = ababab ab3 = abbb

 iteración de ab  iteración de b

x= ab x0 =  x1 = ab x2 = abab x3 = ababab

Operaciones con Hileras 

Inversa de una palabra Se obtiene de escribir los símbolos de una palabra en orden inverso.  Notación: p-1  Si p=a1 a2 ... an entonces p-1 = an an-1 ... a1 (p-1 )-1 =p  (p-1 )i = (pi )-1 para todo i=0,1, .... 

Ejemplo x= abc x-1 = cba

Operaciones con Hileras 

Subhilera: dada la hilera x, y es una subhilera de x si existen r y s tales que x = rys  Todo elemento o símbolo perteneciente a una hilera es una subhilera.  La hilera vacía  es una subhilera de toda hilera.  Subhilera prefijo: es una hilera de cualquier número de símbolos a la izquierda de la hilera.  Subhilera sufijo: es cualquier número de símbolos a la derechos. Ejemplo x= abb y = , y = a y = ab, y = abb

Ejemplo x= abb y = , y = b y = bb, y = abb

Conceptos de Vocabulario   

Vn denota el conjunto de todas las palabras de longitud n sobre V. Un elemento de Vn será una cadena del tipo a1a2...an donde cada ai V. El conjunto de todas las palabras de cualquier longitud que se pueden formar con un alfabeto se denota por V*. 

V *  V n n 0



Es decir, si V es un vocabulario, V* denota el conjunto de todas las hileras compuestas por símbolos de V incluida la hilera vacía.  El conjunto es infinito, pero enumerable. Se denomina cerradura de Kleene del vocabulario  V+ = V* – {} Ejemplo Ejemplo V= {0,1} V= {0,1} V* = {, 0, 1, 00, 01, 10, 11, 000, 111, 011, 100, …} V+ = {0, 1, 00, 01, 10, 11, 000, 111, 011, 100, …}

Lenguaje aaabbb

 



aabb

ab

Es un conjunto arbitrario de hileras de V* aaaabbbb y se denota L. L={xnyn / n  0} Puesto que un lenguaje es tan sólo una clase especial de conjunto, se puede especificar un lenguaje por extensión enumerando sus elementos entre llaves o por comprensión de la siguiente forma: L = {w  V∗ | w cumple la propiedad P}

El lenguaje vacío contiene únicamente la hilera vacía. Notación:    = {} 

Operaciones con Lenguajes Sean L1 y L2 dos lenguajes definidos sobre el alfabeto V.



Unión

L1  L2 = {p/p  L1  p  L2}



Intersección

L1  L2 = {p/p  L1  p  L2}



Diferencia

L1 - L2 = {p/p  L1  p L2}



Complemento El complemento de L con respecto a V* se define como:

L = V* - L = {p  V*  p L}

Operaciones con Lenguajes La unión de lenguajes sobre el mismo alfabeto es un operación cerrada Cumple las propiedades: • • •

Asociativa Conmutativa Elemento neutro que es el lenguaje vacío  (no es lo mismo  que el lenguaje que contiene la palabra vacía {λ}).

Operaciones con Lenguajes 

Concatenación

L1 . L2 = { p1 p2 / p1  L1  p2  L2 }



Asociativa

L1 .(L2 .L3) = (L1 .L2).L3  Elemento Neutro:  = {} L.=.L=L 

No conmutativa

L1 .L2  L2 .L1



Leyes distributivas

L1 .(L2  L3) = (L1 .L2)  (L1 .L3) L1  (L2 .L3) ≠ (L1  L2) . (L1  L3) L1 . (L2  L3) ≠ (L1 .L2)  (L1 .L3) L1  (L2 .L3) ≠ (L1 L2) . (L1 L3)

Operaciones con Lenguajes 

Potenciación: si un lenguaje es elevado a la k-esima potencia se tiene:  Lk = L.Lk-1

si k = 0 si k > 0

Ejemplo L= {a,b} L0 =  L1 = L.L0 = {a,b}. {} = {a,b} L2 = L.L1 = {a,b}. {a,b} ={aa,ab,ba.bb} L3 = L. L2 = {a,b}. {aa,ab,ba.bb} = {aaa,aab,aba,abb,baa,bab,bba,bbb}

Operaciones con Lenguajes 

Clausura  Reflexiva y Transitiva (llamada cerradura de Kleene): es el conjunto de todas las hileras finitas construidas con los elementos de L, incluyendo la hilera vacía. Es el lenguaje Universal: L* En otras palabras contiene: 

La palabra vacía. El conjunto L.



Todas las palabras formadas por la concatenación de miembros de L*.



 L* =  Li = L0  L1  L2 …  i 0

Ejemplo L= {a,b} L* = {,a,b,aa,ab,ba.bb, aaa,aab,aba,abb,baa,bab,bba,bbb,…}

Operaciones con Lenguajes Clausura Reflexiva y Transitiva Esta definición es recursiva, pues en la tercera regla estamos suponiendo que ya hay palabras en L*, las cuales concatenamos para producir una nueva palabra. Esta noción se puede conceptualizar fácilmente de la siguiente forma: Supongamos que inicialmente L* contiene sólo la palabra vacía y los elementos de L. Entonces de ahí tomamos dos elementos cualesquiera, que no necesitan ser distintos, y los concatenamos, para producir una palabra, la cual la añadimos a L* si no estaba ya. Continuando indefinidamente con esta acción, se iran obteniendo todos los elementos de L* .

Operaciones con Lenguajes 

Clausura 

Transitiva: denotado con L+  L+ =  Li = L1  L2 …  i 1

L+ = L* -  o bien L+ = L* - {}

Ejemplo L= {a,b} L+ = {a,b,aa,ab,ba.bb, aaa,aab,aba,abb,baa,bab,bba,bbb,…}

Operaciones con Lenguajes 

Longitud: se mide de acuerdo a la cantidad de hileras que componen el lenguaje. 



Notación: L = n

donde n es la cantidad de palabras

Inversa: Se obtiene con todas las palabras inversas del lenguaje.  Notación: L-1  L-1 = {p-1 / p  L}  (L-1 )-1 =L  (L-1 )i = (Li )-1 para todo i=0,1, ....