Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Trabajo Práctico N°2: Autómatas Finitos
Unidad(es) de Aprendizaje(s)
Unidad(es) programática(s) enmarcada(s) en esta actividad:
Unidad 2. Análisis léxico
Resultado(s) de Aprendizaje(s)
El resultado de aprendizaje que se pretende lograr con este práctico es:
Construye analizadores léxicos para distintos lenguajes regulares utilizando la teoría de
autómatas finitos y expresiones regulares
Presentación
Este práctico se compone de varios ejercicios relacionados con algunos de los conceptos
de la unidad 2 de la materia referidos a la teoría de autómatas.
Es un trabajo práctico individual que se puede desarrollar en papel y/o computadora,
pero debe ser presentado en formato PDF a través del aula virtual.
Descripción de las actividades o consignas de trabajo
Ejercicio 1)
Diseñe un autómata finito que reconozca los siguientes lenguajes:
a) Siendo Σ= {z, y}, L = El conjunto de cadenas que cumplen al menos una de las
siguientes condiciones:
• finaliza con yy
• contiene la subcadena zy
b) L = El conjunto de cadenas que contienen un número par de b y un número impar
de a siendo Σ= {a, b}.
c) L = {x02k+1b | x ε {a,b,c} y x tiene por lo menos una b y k≥0}
Ejercicio 2)
Para el siguiente enunciado modelizar la solución usando un autómata finito:
Se desea programar un robot de manipule una cocina microondas de tal manera que
pueda descongelar o calentar un plato o una fuente con comida. El robot abre la puerta
del microondas cuando recibe el símbolo # y a continuación ingresa un plato (P) o una
fuente (F) con comida. A continuación se indica la operación descongelar (D) o calentar
(C) y el tiempo expresado en minutos (tiempo máximo 59 minutos). Luego, se puede
elegir nuevamente descongelar o calentar y finalmente terminar.
Las entradas posibles para simular este sistema, serán las siguientes:
• #: abrir la puerta del microondas
• P: plato de comida
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
• F: fuente de comida
• C: calentar
• D: descongelar
• F: terminar
Ejemplos:
Las siguientes cadenas son válidas:
• #PD10T descongela un plato de comida durante 10 minutos
• #FD25C3T descongela una fuente con comida durante 25 minutos y la calienta
durante 3 minutos
• #FC25C5T calienta una fuente durante 25 minutos y vuelve a calentar 5
minutos más
Las siguientes cadenas no son válidas:
• #PPC5T no puede ingresar dos platos
• #PC63T no puede calentar por más de 59 minutos
Ejercicio 3)
Complete la tabla poniendo una cruz en aquellas opciones correctas siendo el siguiente
autómata finito:
M = ({S0, S1, S2, S3}, {a, b}, δ, S0, {S3})
δ(S0, a) = {S1}
δ(S0, b) = {S1,S0}
δ(S1, a) = {S1, S0, S2}
δ(S1, b) = {S1,S2}
δ(S2, a) = {S0}
δ(S2, b) = {S1,S0,S3}
δ(S3, a) = {S1}
δ(S3, b) = {S0}
y las posibles opciones:
Opción a) El siguiente autómata finito determinista es equivalente a M.
M' = ({A,B,C,D,E,F}, {a, b}, δ, A, {F})
δ(A, a) = {C} δ(D, a) = {D}
δ(A, b) = {B} δ(D, b) = {F}
δ(B, a) = {D} δ(E, a) = {D}
δ(B, b) = {D} δ(E, b) = {F}
δ(C, a) = {D} δ(F, a) = {D}
δ(C, b) = {E} δ(F, b) = {F}
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Opción b) El siguiente autómata es equivalente a M.
Opción c) El siguiente autómata es equivalente a M:
δ(A, a) = {C} δ(D, a) = {D}
δ(A, b) = {B} δ(D, b) = {F}
δ(B, a) = {D} δ(E, a) = {D}
δ(B, b) = {D} δ(E, b) = {F}
δ(C, a) = {D} δ(F, a) = {D}
δ(C, b) = {E} δ(F, b) = {F}
Opción d) No existe un autómata finito determinista equivalente.
Opción e) El siguiente autómata finito determinista es equivalente a M:
Tabla de respuestas:
Opción a Opción b Opción c Opción d Opción e
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Ejercicio 4)
Diseñe el autómata finito determinista equivalente al siguiente:
0 1
→ Q0 Q4 Q1
Q1 { Q1 , Q2 } { Q3 , Q4 , Q5
}
Q2 { Q0 , Q6 }
Q3 { Q2 , Q5 } Q6
Q4
Q5 { Q3 , Q4 } { Q1 , Q2 }
(F) Q6 { Q3 , Q4 , Q5 } Q6
Ejercicio 5)
Sean M1 el autómata de la izquierda y M2 el autómata de la derecha.
Sea L el lenguaje del alfabeto Σ = {a, b} formado por todas las cadenas que tienen dos b
consecutivas.
Indique cuáles de las siguientes afirmaciones son verdaderas:
a. L(M1) = L
b. L(M2) = L
c. L(M1) = L(M2)
d. M1 es no determinista
e. M2 es no determinista
f. Ninguna de las anteriores
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Recursos y lugar de aprendizaje
Los recursos que debe utilizar para realizar este práctico son:
● Lección: Autómatas Finitos y Autómatas Finitos No Deterministas (aula virtual)
● Material provisto por la cátedra (aula virtual)
● Bibliografía básica referida a la Unidad 2 (ver propuesta de cátedra)
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Evaluación
En este práctico se evaluarán los siguientes criterios:
No
presentado No logrado En proceso Logrado Excelente
/ contestado
Porcentaj
0 4 6 8 10
e
El alumno no El alumno El alumno
El alumno
Diferencia los comprende lo que comprende AF pero comprende AF y
No comprende AF y
mecanismos que son los AF ni puede no puede puede
30% entregado. sólo detecta los
describen lenguajes diferenciar entre diferenciar entre diferenciar entre
AFND o los AFD.
regulares AFND y AFD. AFND y AFD. AFND y AFD.
0 1.2 1.8 2.4 3
El alumno puede El alumno puede
El alumno no puede El alumno puede
Modela distintos modelar la mayoría modelar todos
No modelar ningún modelar algunos
problemas utilizando de los problemas los problemas
40% entregado. problema con problemas con
los mecanismos con autómatas con autómatas
autómatas finitos. autómatas finitos.
adecuados finitos. finitos.
0 1.6 2.4 3.2 4
El alumno aplica
El alumno obtiene El alumno aplica de
de manera
Aplica correctamente El alumno no aplica el AFD equivalente manera incorrecta
No correcta los
métodos para la ningún mecanismo sin aplicar ningún los mecanismos de
30% entregado. mecanismos de
conversión entre de conversión. mecanismo de conversión de AFND
conversión de
distintos mecanismos conversión. a AFD.
AFND a AFD.
0 1.2 1.8 2.4 3
Facultad de Ingeniería - Ingeniería en Informática
Cátedra de Compiladores – Año 2023
Tiempo estimado de realización
El tiempo estimado para completar este trabajo es:
Horas presenciales 4 hs.
Horas de trabajo autónomo 6 hs.
Tiempo total 10 hs.
Formato y fecha de entrega
El práctico debe entregarse antes del 23 de agosto (hasta las 23.59hs) en formato PDF a
través de la plataforma. NO se recibirán entregas por e-mail. Las dudas y aclaraciones
sobre el enunciado se resolverán a través del foro.
Nota: Propiedad intelectual
Al presentar un práctico que haga uso de recursos ajenos, se detallarán todos ellos, especificando
el nombre de cada recurso, su autor, el lugar donde se obtuvo y su estatus legal: si la obra está
protegida por copyright o se acoge a alguna otra licencia de uso (Creative Commons, licencia GNU,
GPL ...). El estudiante deberá asegurarse de que la licencia no impide específicamente su uso. En
caso de no encontrar la información correspondiente deberá asumir que la obra está protegida por
copyright.
