UNIVERSIDAD NACIONAL DE SANTIAGO DEL ESTERO

2013

ACTIVIDADES PRÁCTICAS

CUADERNILLO DE

Facultad de Ciencias Exactas y Tecnologías

Teoría de la Computabilidad 2013 1. Determine si las formalizaciones1 son adecuadas para los enunciados de problemas: Formalización

Enunciado del problema

D=Z 1.1. Determinar si un número es I = N perfecto. (Un número es perfecto R = y / y = “sí ”  y = “ no ”  si es igual a la suma de todos sus divisores excluido el mismo q =  ( x , y )  I x R / [y = “ si ”  x: x = número: 6 = 1 + 2 + 3).

k

x i 1

; donde xi = j

i

 x mod j = 0 con j = 1.. x-1, con i = 1… i+1… k]  [y = “no”  todo lo contrario]. D=N 1.2. Determinar capicúa.

si

un

número

es

I =  x / x  N  x = x1 x2 ...xn  n  2  R = y / y = “sí ”  y = “ no ”  q =  ( x , y )  I x R / y = “ si ”  x : xi = xj con i = 1, 2, ... , Int (n/2)  j = n, n-1 , ... , Int (n/2)  y = “ no ”   x : xi  xj con i = 1, 2, ... , Int (n/2)  j = n, n-1 , ... , Int (n/2) 

1.3. Determinar si un número entero positivo de m dígitos (con 2 =0] L = {anbm / n+m es par} L = {abnw/ n  3, w  {a,b}*} L = {vwv/ v, w  {a,b}*, v=2} L = {x / x  {0, 1}*  x termina en 00} L = {x /x  {a,b}*  x no contiene aa ni bb como subcadenas}. L = {x /x  {a,b}*  x contiene una cantidad de a que es múltiplo de 3} L = { an b2m c2ñ+1 | m, n, ñ ≥ 1} L = { w  {a,b,c}* / w contiene exactamente una ocurrencia de la cadena aaa} El lenguaje de todas las secuencias no vacías que se pueden formar con signos más y letras mayúsculas respetando las dos condiciones siguientes: no habrá dos signos más consecutivos ni

tampoco dos letras consecutivas. Por ejemplo: +U+J+I+. m) L = {x = aibj  x = (cd)2n+1, i  0, n, j  1} n n) L = {x/x = awc , n 1,w  {a, b}*} o) El lenguaje de todas las secuencias que pueden formarse utilizando únicamente dígitos decimales y

asteriscos con la restricción de que en la cadena debe haber un único grupo de varios asteriscos consecutivos. 6.

Definir las gramáticas y expresiones regulares que generen: a) Constantes enteras con signo, sin ceros no significativos b) Constantes reales con notación exponencial c) Identificadores de cualquier longitud que comiencen con una letra y contengan letras, dígitos o

guiones. No puede terminar con guión. d) Comentarios acotados por /* y */ sin que intervenga */ a menos que aparezca entre comillas.

7.

Definir gramáticas libres de contexto5 para los siguientes lenguajes, siempre que sea posible:

a) b) c) d) 8.

L1 = {xnyn}{x2nyn} L2 = {xmyn | 0  n  m  3n} L3 = {xmynzp/ m, n, p 0  m+n=p} L4 = {xnym | mn2m}

Para cada uno de los siguientes lenguajes, definir la gramática libre de contexto: a) L = {anbm / n,m  0  n  m+3} b) Un lenguaje de paréntesis, llaves y corchetes bien balanceados. Por ejemplo, las palabras “()[]”, “([])” y “()[[]]” son correctas, mientras que “[[]” y “([)]” no lo son. Nótese que en esta última palabra los paréntesis solos están balanceados, así como los corchetes solos, pero su combinación no lo está. c) L = {anbmck/ n,m,k  0  ( n = m  m  k} d) L = {anbmck/ n,m,k  0  k = n + m} e) L = {anbmck/ n,m,k  0  k = n + 2m } f) L = {wcw-1/ w  {a,b}*} g) L = {anbmck/ n  0, k  1  m = n + k} h) L = {a3bncn/ n  0} i) L = {anbm/ n, m  0  n  m -1} j) L = {anbm/ n, m  0  2n  m  3n} k) L = {anbmck/ n,m,k  0  (n =m  m  k)} l) L = {anbmck/ n,m,k  0  k  n+m} m) L = {ab(ab)nb(ba)n/ n  0 }

5

Estas gramáticas, conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico. En el lado izquierdo de las reglas de producciones aparece o el símbolo distinguido o un no terminal, mientras que en el lado derecho de una producción cualquier cadena de símbolos terminales y/o no terminales de longitud mayor o igual que 1.

Teoría de Lenguajes Formales y Gramáticas n) o) p) q) r) s) t) u) v) 9.

2013

L = {w / w  {a,b,c}*  #a(w) + #b(w) =#c(w)} L = {anbm/ n, m  0  n  2m } L = {w / w  {a,b}*  #a(w)  #b(w)} L = {w / w {a,b}*  #a(v)  #b(v), siendo v cualquier prefijo de w} L = {w / w {a,b,c}*  #a(w) + #b(w)  #c(w)} L = {w / w {a,b,c}*  #a(w) = #b(w) +1} L = {w / w {a,b,c}*  #a(w) = 2#b(w)} L = {w1cw2 / w1 , w2 {a,b}*  w1  w2R} Expresiones regulares sobre el vocabulario {a,b}.

Determinar si cada uno de los siguientes lenguajes es libre de contexto o no. Justifique su respuesta: a) b) c) d) e)

L = {anwwRan / n  0, w  {a,b}*} L = {xyz / x=y=z  xa = ya = za } L = { anbnci/ n  i  2n } L = { anbm/ m,n  0, (m=n)  (m=2n) } L – {w1 w2 w3 w4 / w1 w3 = aibj, w2w4 = cjdj ; i,j  0}

10. Considere la gramática: G = ({S,A}, {a,b}, P, S) donde P es: S  AA A  a/ bA/ Ab a) ¿Qué cadenas de L(G) se pueden generar con derivaciones de cuatro pasos o menos? b) Dé al menos cuatro derivaciones distintas para babbab y dibuje los árboles de derivación correspondientes (los cuales podrían no ser distintos). 11. Dada la siguiente gramática: G = ({S,A,B}, {a,b,c}, P,S) donde P es: S  aBA / c A  bS B  Sb Para la cadena aacbbcbbc encontrar: i. Una derivación más a la izquierda ii. Una derivación más a la derecha i. El árbol de derivación 12. Describir los lenguajes generados por las siguientes expresiones regulares y definir las correspondientes gramáticas regulares: a)

01 (((10)*/111)*/0)*1

b) ((ba)* / (ab)*)*

c)

(11/0)*(00/1)*

d) b/(a+b/a+)

e)

(aaa / aaaaa)*

f)

(aa)* •(bb)*

g) 10/(0/11)*0*1

h) (0/1)(0/1)*00

i)

j)

(0/1)(0/1)* ((0/1)(0/1)(0/1))*

13. Dadas las expresiones regulares E1 = a* / b* y E2 = ab* / ba* / b*a / (a*b)*, encuentre: Una hilera que pertenezca a E2 pero no a E1 Una hilera que pertenezca a E1 pero no a E2 Una hilera que pertenezca a E1 y a E2 Una hilera que no pertenezca ni a E1 ni a E2

(10)[((10)*/111)*0]*1

Teoría de Lenguajes Formales y Gramáticas

2013

14. Escriba expresiones regulares equivalentes a las siguientes lo más simplificadas que sea posible: a)

((a*b*)*(b*a*)*)*

b) (a / b)*a(a / b)*

c)

(a*b)* / (b*a)*

d) a* / b* / (a + b)*

15. Dadas las siguientes gramáticas, muestre que son ambiguas 6: a)

S  SS+ / SS* / a

b) S  S (S) S / 

S  a / S+S / SS / S* / (S)

16. Dadas las siguientes gramáticas factorice: a)

S  abA / abB A  aAb / ab B  bBa / ba

S  aBcC / aBb / aB / a B d

17. Dadas las siguientes gramáticas, eliminar la recursividad a izquierda directa e indirecta: a)

S  (L) / a L  L,S / S

e) S SS /CA / A A bAA / aC / a B  aSS /BC / B C  CC /C

6

b) S  SS / (S) / 

c)

S  Sa / Bb / Cc /  B  Bb / Cc /  C  Cc / 

d) S  Aa / b A  Ac / Sb / c

f)   + | - | λ  |  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Una gramática es ambigua si el lenguaje tiene alguna hilera que tenga más de un árbol sintáctico. Es posible frecuentemente, modificar la gramática para que deje de ser ambigua.

Teoría de Autómatas 2013 A.

AUTÓMATAS FINITOS7

1. Para el siguiente diagrama de transición a)

Definir el autómata finito.

b)

Obtener la gramática.

c)

Dar ejemplos de hileras reconocidas por el autómata. 0

1

0, 1

q0

0

q1

q2

0

1

2. Diseñar un Autómata Finito que, reconozca el lenguaje formado por cadenas de números binarios y que posean subhileras de la forma 1011. Nótese que si la cadena fuera, por ejemplo, 0101011011011, se detectaría dos ocurrencias de la palabra clave (subrayadas), no considerando el “1” de la séptima posición como inicio de otra ocurrencia. 3. En algunos lenguajes de programación, los comentarios aparecen entre los delimitadores “/*” y “*/” como marca inicial y final del comentario. Sea L el lenguaje de todas las cadenas de comentarios delimitados. Así pues todo elemento de L, empieza por /* y acaba por */, pero no debe tener ningún */ intermedio. Por simplicidad consideraremos que el alfabeto sería {a, b, /,*}. Indicar el Autómata Finito Determinista que reconoce L. 4. Para los siguientes diagramas de transición a) Defina el autómata finito. b) Obtenga la gramática, la expresión regular y el lenguaje b

a

M1

a

q0

M2

b

q1

a

q2

a

q0

0

q1

a ,b a

q2

b

b

M3

a ,b

0

q0

1

1

q1 0

q2

0

0

5. Realizar los diagramas de transición correspondientes a los ejercicios de la guía de gramáticas regulares.

7

Recordar que un Autómata Finito (AF) se define formalmente como una quíntupla: A= (conjunto finito no vacío de estados, alfabeto finito de entrada, función de transición directa, estado inicial, conjunto de estados finales). Puede representarse mediante una tabla de flujos o una diagrama de transición. Además, se dice que el Autómata Finito es No Determinístico cuando existe más de una función de transición para un mismo símbolo de entrada. Los conceptos generales están extraídos de Barchini, Graciela y Alvarez Margarita - Fundamentos Teóricos de la Ciencia de la Computación, Departamento de Informática. FCEyT 1994 y 1998.

Teoría de Autómatas 2013 6. Para los AFND del ejercicio 4 obtenga el equivalente determinístico. 7. Definir y graficar los autómatas finitos de estados mínimos equivalentes a los dados.

B.

AUTOMÁTAS DE PILA 8 ó PUSH-DOWN AUTÓMATAS

1. Dados los siguientes lenguajes, realice los autómatas de pilas correspondientes.

a) L(G) = {anbnc / n  1} AP SGO

b) L(G) = { anb2nc/ n  0}

c) L(G) = {ambmcn / n,m  1}

d) L(G) = {ambncn / n,m  1}

e) L(G) = {anbmcmdn / n,m  0} f) L(G) = {anbm / n  m} AP SGO

g) L(G) = {aibjck / i = j o j = k} AP SGO

h) L(G) = {anbmcn+md / n,m  1}

i) L(G)={ xwx-1 / x  {a,b}*, w  {c,d}+}

j) L(G) = {(ab)n cn (dd)j /n  1, j  0}

k) L(G) = {0m1n0m+n / m,n  0}

l) L(G) = {anbncn+md / n,m  1}

m) L(G) = { anbmc3m+1d2n / n,m  1}

n) L(G) = { aibjck / i=2j o k=3j-1}

o) L(G) = {anbicd2(n+m) / n,m  1; i  0}

p) Lenguaje que genere hileras de ceros y unos con igual cantidad de ceros y unos. q) Lenguaje que genere hileras de a y b con distinta cantidad de a que de b. r) Lenguaje formado por paréntesis balanceados. 2. Realice los autómatas que reconozcan hileras pertenecientes a los lenguajes libres de la guía de “Teoría de Lenguajes y Gramáticas”. C. 8

MÁQUINAS DE TURING9

Un autómata de pila es un dispositivo abstracto que formalmente se define mediante una 7-upla:A =(conjunto finito no vacío de la unidad de control, alfabeto de entrada, alfabeto de la pila, función de transición directa, estado inicial, símbolo inicial de la pila, conjunto de estados finales). La notación cambia notablemente sobre las transiciones, pues involucran: símbolo que se lee, símbolo del tope de pila, acción a seguir. Si la acción a seguir es borrar un elemento de la pila, se escribe λ. Si la acción es apilar, se escribe el símbolo que se guardará en la pila y el símbolo actual del tope de pila. Si no se hará nada, sólo se consigna el tope de pila. 9 Formalmente una Máquina de Turing (MT) se define como una 6-upla: A=(conjunto finito no vacío de la unidad de cinta, alfabeto de entrada no vacío, alfabeto de la cinta, función de transición, estado inicial, conjunto de estados finales). La particularidad de la cabeza lecto-escritora de la MT es que se puede mover a derecha, a izquierda, o no moverse.

Teoría de Autómatas 2013 1. Defina una máquina de Turing que reconozca los siguientes lenguajes:

a) L(G) = {0n1n2n / n  1}

b) L(G) = {x#x / x  {a,b,c}*}

c) L(G) = {anbmcnm /m, n  1}

d) L(G) = {a2n/ n  1}

e) L(G) = {an bm an+m / n, m  0}

f) L(G) = {an bn-1 cn+3 / n  1} h) L(G) = {x/ x  {0,1}* y la cantidad de ceros es igual a la cantidad

g) L(G) = {12k+1 / k  0} i) 2.

L(G) = {ww-1 / w  {0,1}*}

de unos}

j) L(G)={ xwx-1 / x  {a,b}*, w  {c,d}+}

Diseñe una máquina de Turing unicinta y/o multicinta que: a. Multiplique dos números en notación unaria. b. Reciba dos números en código unario, separados por un espacio en blanco, y devuelva su suma. c. Calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s). d. Obtenga el sucesor de un número en codificación unaria. Considerar en la codificación unaria que el 0 se representa por la cadena vacía, el 1 por 1, el 2 por 11, etc. e. Calcule la paridad de un número binario. Es decir, si el número de 1’s de la cadena es par, se añade un 0 al final, y si es impar, se añade un 1.

8. Los AF en la vida real Los siguientes escritos breves dan cuenta de la funcionalidad de los AF en la vida reali: Situación 1: En biología son muy usados para modelar ciertas cosas. Se pueden crear AF como modelos de

cómo responde una célula ante un estímulo. Se tiene un input que puede ser un químico o algo similar, una serie de estados que pueden ser los estados de expresión de ciertos genes, o la producción de alguna proteína y además ciertas probabilidades de transición. En sí, se piensa que una célula en su totalidad se puede modelar como un autómata finito no determinista.

Situación 2: Para ciertos procesos celulares que requieren mucho control, como el crecimiento embrionario,

se pueden usar autómatas finitos deterministas (como una simplificación) para modelar los cambios de expresión de los genes que hacen que el proceso de gestación se lleve a cabo. Situación 3: Se pueden usar expresiones regulares cuando de un texto extenso interesa saber cuándo se

mencionan ciertas palabras. Por ejemplo, en la Biblia, para extraer sólo la información de dónde estuvo Jesús, se puede generar una expresión regular en la que se busquen ciertas estructuras gramaticales de oraciones que relacionen a Jesús con algún lugar.

Una de las aplicaciones de la prueba de Turing es el control de spam. Dado el gran volumen de correos electrónicos enviados, el spam es, por lo general, enviado automáticamente por una máquina. Así la prueba de Turing puede usarse para distinguir si el correo electrónico era enviado por un remitente humano o por una máquina (por ejemplo por la prueba Captcha). Captcha es el acrónimo de Completely Automated Public Turing test to tell Computers and Humans Apart (Prueba de Turing pública y automática para diferenciar máquinas y humanos).

i

Fuente: http://espanol.answers.yahoo.com/question. Accedida en septiembre de 2010.