07:53

00

Temas  Símbolo, alfabeto  Hileras y operaciones con hileras  Operaciones con lenguajes

Objetivo Que el estudiante logre conocer, comprender y manejar conceptos vinculados con la Teoría de Lenguajes Formales y realizar operaciones con hileras y lenguajes.

07:53

11

 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.

07:53

22

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 07:53

significa la disyunción de las proposiciones p y q 33

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 {, }, |

07:53

44

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.

07:53

55

 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 = {, , . . . , } 07:53

66

 Es cualquier string de longitud finita compuesto por símbolos sobre el vocabulario. Es un conjunto finito de símbolos yuxtapuestos. x es una hilera sobre V, si y solo si x = x1 … xn donde xi  V, i = 1, …, n

 Longitud de una hilera: es la cantidad de símbolos que componen esa hilera. Ejemplo ─ Notación: |x| para una hilera x. V = {a, b} ─ Es decir, si x = x1 … xn entonces |x|=n. x= a y = b  Hilera o palabra vacía: es la cadena de longitud cero. ─ Notación:  o  Ejemplo ─ Longitud de  es 0 x = perro  |x| = 5 07:53

x = abba  |x| = 4

77

 Vn denota el conjunto de todas las hileras 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 hileras 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 V= {0,1} V* = {, 0, 1, 00, 01, 10, 11, 000, 111, 011, 100, …} 07:53

Ejemplo V= {0,1} V+ = {0, 1, 00, 01, 10, 11, 000, 111, 011, 100, …}

88

Concatenación

 

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

Ejemplo x= abb y = bac xy = abbbac

Es asociativa: Ejemplo x(yz) = (xy)z x= ab y = bc z=de No conmutativa: ab(bcde) = (abbc)de xy ≠ yx Posee elemento neutro:  x=x=x Ejemplo x  y = xy x= abb y = bc Longitud de concatenación abbbc ≠ bcabb |xy| = |x|+|y| Es una operación cerrada  x,y  V*: x . y  V* 07:53

99

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: Ejemplo  si n = 0 x= ab n n-1 w.w si n > 0 x0 =  x1 = ab x2 = abab 3 = ababab x • Es necesario usar paréntesis cuando sea necesario.

w =

Ejemplo (ab)3 = ababab ab3 = abbb 07:53

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

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, ....

07:53

Ejemplo x= abc x-1 = cba

11 11

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 prefijo Ejemplo sufijo 07:53

x= abb y = , y = a y = ab, y = abb

x= abb y = , y = b y = bb, y = abb12 12

Homomorfismo : Otra operación importante es el homomorfismo que es conmutativa con respecto a la concatenación en el siguiente sentido: para todo par de palabras P, Q V* la imagen homomórfica de la concatenación, esto es h(PQ) es lo mismo que la concatenación de sus imágenes h(P) y h(Q) h(PQ) = h(P) h(Q) P y Q V* Mapeo: sea V1 y V2 dos alfabetos. Entonces el mapeo h de V1* en V2* se llama homomorfismo si cumple con las siguientes propiedades: 1) h es única, esto es, para cada P en V1* hay exactamente una palabra W en V2* con W = h(P). 2) h(PQ) = h(P)h(Q) para todo P,Q en V1*. Estas dos propiedades significan que h( ) = . Es decir, para cada P en V1* h(P) = h( P) = h() h(P) 07:53

13 13

El homomorfismo h se llama isomórfico si para todo P y Q con h(P) = h(Q) implica P=Q. El caso especial de isomorfismo surge cuando la imagen de los símbolos de V1 son símbolos en V2. Tal isomorfismo es simplemente una transformación de V1 a V2.

Ejemplo Código decimal binario representado por los enteros donde: V1 = {0,1,...9} V2 = {0,1} y h(0) = 0000 h(1) = 0001 h(2) = 0010 ... h(9) = 1001 El homomorfismo es muy útil en esta teoría, por ejemplo para generar gramáticas equivalentes.

07:53

14 14

 Dado el siguiente lenguaje determinar qué símbolos pertenecen al metalenguaje y cuáles al lenguaje objeto. a) L = { xZm | Z = + y; m  0 }  Sea x = 0101; calcular: a) x-1 b) x0 c) x1 d) x2  Sea x = acb y y = aba ; calcular: a) xy b) (xy)-1 c) y-1x-1 d) x e) y f) x y g) x2 y2 07:53

15 15

aaabbb

Es un conjunto arbitrario de hileras de V* y se denota L.

aabb

ab

aaaabbbb

L={anbn / n  0}

Extensión: enumerando sus elementos entre llaves Lenguaje

Comprensión: L = {w  V∗ | w cumple la propiedad P}

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

16 16

 L1 = {a, b, }. Palabras a, b y la cadena vacía.  L2 = {aibi / i ≥0}. Palabras formadas de una sucesión de símbolos a, seguida de la misma cantidad de símbolos b. i

Hileras

0



1

ab

2

aabb

3

aaabbb

 L3 = {uu-1 / u {a,b}*}. Palabras formadas con símbolos a y b y que consisten de una palabra, seguida de la misma palabra escrita en orden inverso. Hileras  abba 07:53

abbbba

17 17

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} 07:53

18 18

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 {λ}).

07:53

19 19

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

Ejemplo L1 = {ca,ma} y L2 = {nta, sa} L1L2 = {canta, casa, manta, masa}. Para calcular la concatenación de dos lenguajes hay que concatenar cada palabra del primero de ellos con cada una del segundo.

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)

07:53

20 20

Potenciación: si un lenguaje es elevado a la k-ésima 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} 07:53

21 21

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: 1. La palabra vacía. 2. El conjunto L. 3. Todas las palabras formadas por la concatenación de miembros de L*. 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 Ejemplo puede conceptualizar fácilmente de la siguiente forma: L= {a,b} Supongamos que inicialmente L* contiene sólo la palabra vacía y los elementos de L. L* =de{,a,b,aa,ab,ba.bb, aaa,aab,aba,abb,baa,bab,bba,bbb,…} Entonces 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 irán obteniendo todos los elementos de L* . 07:53

22 22

 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,…} 07:53

23 23

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, ....

07:53

24 24



Dar ejemplos de hileras x  L:    





07:53

L={ambmcn ; m, n 1} L={xcx-1 / x  {0,1}*} L={anbm ; n m  2n} L={x / x {a,b}+ y x contiene un número impar de a's}

Dado los lenguajes A={a,c} y B= {a,b} calcular:  BA  BA  B.A  B.A+  (B.A)*  B.  Definir lenguajes para:  Lenguaje sobre el alfabeto {0,1} con todas las hileras que finalicen con 1.  Lenguaje formado por hileras y su palíndroma. 25 25

Definido a partir de Alfabeto (V)

Conjunto (V*)

Es un subconjunto de

Hilera

Tiene Operaciones Concatenación (w1.w2) Potencia (wn) Inversa (w-1) Subhileras 07:53

Lenguaje

Tiene Operaciones Concatenación (L1.L2) Potencia (Ln) Inversa (L-1) 26 26

Gramáticas Formales

G = (VN, VT, P , S)

Lenguajes Formales Autómatas

A =(Q, , , q0, F)

Jerarquía de Chomsky

Los lenguajes más formalizados como los lenguajes de programación o el lenguaje matemático, tienen unas estructuras claramente definidas y determinadas por sus reglas gramaticales (sintácticas y semánticas). Esto ha posibilitado y propiciado la construcción de traductores 27 automáticos para estos lenguajes. 07:53 27