SSL_TP4_ENUNCIADO_2020

Vista previa del material en texto

UNIVERSIDAD TECNOLÓGICA NACIONAL 
Facultad Regional Tucumán 
Departamento: SISTEMAS 
Cátedra: Sintaxis y Semántica de los Lenguajes 
Ciclo 2020 
TRABAJO PRÁCTICO 
Nº 4 
 
 Página 1/3 
 
UNIDAD Nº 4: Lenguajes, Gramáticas y Modelos Generales. 
Los aceptores de lenguajes formales generales: Máquina de Turing (MT) y Autómata Li-
nealmente Limitado (ALL). MT transformadora de secuencias, multicinta y multicelda. 
 
 
 
 
1.1. Obtener ALL que acepten los siguientes lenguajes. 
a) L = { an b2n / n ≥ 1 } 
b) L = { an bm cp / n ≥ 0, m > n, p > m } 
 
1.2. Diseñar MT que realicen las siguientes acciones: 
a) duplicar cualquier secuencia de la cinta con ΣE = { a , b } 
b) a partir de una secuencia de la forma ym xn / n,m ≥ 0, agregar a continuación de la 
misma un “0”, “1” o “2” según sea n=m, n>m o m>n, respectivamente. 
 
1.3. Resolver la suma de dos números en sistema binario con MT multipista y con MT multi-
cinta. Simular con JFLAP. Comparar con la solución usando MT de una sola cinta y una 
sola pista. 
 
1.4. Construir una MT por bloques, que acepte el lenguaje con patrón ww, donde w es una 
secuencia cualquiera sobre el alfabeto ΣE = { a , b } 
 
 
 
Nota: En todos los ejercicios hacer la simulación con JFLAP. 
 
GRUPO DE TRABAJO 
Nº de Grupo: División: 
Profesor: Fecha de Entrega 
___/___/___ Auxiliar: 
Orden Apellido y Nombre de los Integrantes Nro. Legajo 
1 
2 
3 
4 
5 
6 
1. Problemas a resolver en clase práctica 
 UNIVERSIDAD TECNOLÓGICA NACIONAL 
Facultad Regional Tucumán 
Departamento: SISTEMAS 
Cátedra: Sintaxis y Semántica de los Lenguajes 
Ciclo 2020 
TRABAJO PRÁCTICO 
Nº 4 
 
 Página 2/3 
 
 
 
 
 
2.1. Diseñar ALL que acepten los siguientes lenguajes para el alfabeto ΣE = { a , b }. 
a) L = { an bm / n ≥ 1, m ≠ n } 
b) L = { complemento del Lenguaje Palíndromo } 
c) L = { todas las cadenas de longitud impar que cumplan que el “símbolo central” sea 
igual al primero } 
 
2.2. Dado ΣE = { 0 , 1 }, desarrollar ALL o MT que realicen las siguientes acciones (indicar en 
qué casos no es posible resolver con ALL y porqué): 
a) realizar el producto de dos números en sistema unario. 
b) a partir de un palíndromo de longitud impar, transformarlo en otro de longitud par 
“duplicando” uno de los símbolos centrales (la nueva secuencia tendrá longitud n+1). 
c) a partir de un palíndromo de longitud par, transformarlo en otro de longitud impar 
“suprimiendo” uno de los símbolos centrales (la nueva secuencia tendrá longitud n-1). 
d) L = { todas las secuencias formadas por los símbolos del alfabeto de entrada }, reali-
zando una transformación que genere como salida la inversa de la palabra. 
 
2.3. Encontrar una MT de 2 pistas, que reciba como entrada dos secuencias de igual lon-
gitud, una en cada pista y elimine los símbolos que resulten igual en ambas pistas, com-
primiendo la secuencia. De tal modo que al final quedarán en la cinta dos secuencias que 
serán de menor o igual longitud que las de partida. ΣE = {a , b}. 
 
Por ejemplo: si la entrada es: , la salida será: 
 
 
2.4. Diseñar MT multicinta que: 
a) Determine el mayor de dos números binarios (haga las suposiciones que crea conve-
niente). 
b) Dada una secuencia cualquiera sobre el alfabeto ΣE = {a, b, c}, indique según el caso: 
el o los símbolos que se repiten más veces, si los tres se repiten la misma cantidad 
de veces, si no hay repeticiones o si se trata de la palabra vacía. 
2.5. Construir una MT por bloques, que acepte el lenguaje con patrón anbncndn. 
2. Problemas a resolver por los alumnos 
a b b a a b 
b b a a b b 
a b a 
b a b 
 UNIVERSIDAD TECNOLÓGICA NACIONAL 
Facultad Regional Tucumán 
Departamento: SISTEMAS 
Cátedra: Sintaxis y Semántica de los Lenguajes 
Ciclo 2020 
TRABAJO PRÁCTICO 
Nº 4 
 
 Página 3/3 
 
 
 
1) Diseñar MT, utilizando la variante más conveniente, para resolver: 
(a) Producto binario. 
(b) Resta binaria usando complemento A2. 
2) Realizar un programa que permita introducir las reglas de una gramática e indique el 
tipo de la misma en la jerarquía de Chomsky. 
 
 
3. Ejercicio de Aplicación