Guía de actividades y rúbrica de evaluación - Unidad 2 - Tarea 3 - Construcción de Autómatas de Pila

Vista previa del material en texto

1 
 
Universidad Nacional Abierta y a Distancia 
Vicerrectoría Académica y de Investigación 
Curso: Autómatas y lenguajes formales 
Código: 301405 
 
Guía de actividades y rúbrica de evaluación – Tarea 3 
Construcción de Autómatas de Pila 
 
1. Descripción de la actividad 
Tipo de actividad: En grupo colaborativo 
Momento de la evaluación: Intermedio 
Puntaje máximo de la actividad: 115 puntos 
La actividad inicia el: 
domingo, 2 de octubre de 2022 
La actividad finaliza el: sábado, 29 
de octubre de 2022 
 
Con esta actividad se espera conseguir los siguientes resultados 
de aprendizaje: 
 
Determinar el diseño de autómatas de pila y gramáticas independientes 
de contexto mediante mecanismos de representación formal, teniendo en 
cuenta la comprensión de las características que cada uno maneja. 
 
 
La actividad consiste en: 
 
• Consultar los contenidos temáticos de la Unidad 2: Lenguajes 
Independientes del Contexto ubicados en el entorno de aprendizaje 
Unidad 2. 
• Responder en el foro de discusión de forma oportuna y adecuada a 
los ejercicios propuestos, de acuerdo con su selección, según 
lineamientos de la guía de actividades propuesta. 
 
A continuación, se encuentra el seguimiento de instrucciones resumidas 
en 6 pasos. Los pasos 1, 2, 3 y 4 se desarrollan de forma individual y los 
pasos 5 y 6, se desarrollan de manera colaborativa entre los 5 integrantes 
del grupo. A continuación, se presenta la descripción de cada paso. 
 
 
 
 
 
2 
 
Pasos de la estrategia de aprendizaje a desarrollar 
 
Paso 1. Revisión de los contenidos de la Unidad 2. El estudiante debe 
ingresar al entorno de aprendizaje Unidad 2 y revisar las referencias 
requeridas para la Unidad. 
Paso 2. Elección en el foro de ejercicios a desarrollar individualmente. 
Los ejercicios se seleccionan según la siguiente tabla: 
 
Tabla de selección de ejercicios 
 
Autómata a Pila 
Ejercicio a. 
Ejercicio b. 
Ejercicio c. 
Ejercicio d. 
Ejercicio e. 
 
Cada estudiante debe seleccionar el rol a desarrollar y un ejercicio a, b, 
c, d o e, a desarrollar. 
 
Posteriormente debe copiar y pegar la tabla siguiente en el foro de la 
Tarea 3, anotando el nombre y el rol a desempeñar en el trabajo. 
 
Tabla de elección de ejercicios: 
 
Nombre del estudiante Rol a 
desarrollar 
Grupo de ejercicios a desarrollar 
paso 1. 
Datos 
Estudiante 1 
Revisor El estudiante desarrolla el 
ejercicio a. 
Datos 
Estudiante 2 
Evaluador El estudiante desarrolla el 
ejercicio b. 
Datos 
Estudiante 3 
Entrega El estudiante desarrolla el 
ejercicio c. 
Datos 
Estudiante 4 
Alerta El estudiante desarrolla el 
ejercicio d. 
Datos 
Estudiante 5 
Compilador El estudiante desarrolla el 
ejercicio e. 
 
Paso 3 – Presentación en el foro de los aportes parte individual. El 
estudiante procede con el desarrollo de los ejercicios seleccionados y 
presenta los aportes en el Foro para el paso 3. Solo se deben presentar 
los aportes de ejercicios seleccionados en la tabla de elección de 
ejercicios. Si un estudiante elige el ejercicio a, solo debe presentar ese 
 
 
3 
 
ejercicio para la parte individual y para la parte grupal debe presentar 
mínimo dos aportes a la solución del ejercicio planteado. 
 
Se deben entregan los aportes durante el tiempo estipulado para esta 
actividad en el foro de la Tarea 3. 
 
Cada aporte debe ser de autoría del estudiante. 
 
Nota: En la carpeta Guía de actividades y rúbrica de evaluación - Unidad 
2 - Tarea 3 - Construcción de Autómatas de Pila. Se encuentra el 
Instructivo 1 - Guía para el uso de recursos educativos - Simuladores VAS 
y JFlap.pdf, en donde encuentra los requerimientos para la ejecución de 
los simuladores. 
 
Paso 4 – Compilación trabajo Individual. Cada estudiante debe 
entregar en el foro el desarrollo de sus ejercicios en un documento Pdf 
con los siguientes elementos: 
• Portada. 
• Desarrollo de los ejercicios 
• Referencias Bibliográficas en normas APA. 
• El nombre del archivo debe ser 301405_(cédula). 
 
Paso 5 – Presentación de aportes a la solución del ejercicio planteado a 
desarrollar de manera grupal. A partir del ejercicio propuesto el grupo 
debe realizar los aportes respectivos en el foro colaborativo con el fin de 
reconocer las características del mismo y deberá buscar el método de 
solución más apropiada para ser presentada como trabajo colaborativo. 
(todos los estudiantes deben presentar dos aportes para este paso). 
 
Paso 6 – Compilación trabajo final. 
En el transcurso de la última semana del trabajo colaborativo, los 
estudiantes del grupo compilan los ejercicios en un documento Pdf con 
los siguientes elementos: 
• Portada. 
• Desarrollo del ejercicio 
• Referencias Bibliográficas en normas APA. 
 
El estudiante que tiene el rol de entrega del grupo lo debe entregar en el 
Entorno de Evaluación en formato pdf y el nombre del archivo debe ser 
301405_ (número del grupo). 
 
 
4 
 
 
El estudiante que entrega el trabajo grupal debe hacer un archivo .zip 
donde estará su entrega individual y la grupal, el nombre del archivo debe 
ser 301405_Final (número del grupo) 
 
EJERCICIOS PARA DESARROLLAR 
 
A continuación, se definen los ejercicios a desarrollar: 
 
Ejercicios 1: Autómata de Pila 
 
a. b. c. 
 
Inicial = q0 
Final q1 
(q0, a, λ) = (q0, a) 
(q0, b, λ) = (q0, b) 
(q0, λ, λ) = (q1, λ) 
(q1, b, b) = (q1, λ) 
(q1, a, a) = (q1, λ) 
 
Inicial = q0 
Final q3 
(q0, λ, z) = (q1, z) 
(q1, x, λ) = (q1, x) 
(q1, y, x) = (q2, λ) 
(q2, y, x) = (q2, λ) 
(q2, λ, z) = (q3, z) 
 
Inicial = q0 
Final = q2 
(q0, 0, B) = (q0, BB) 
(q0, 0, Z) = (q0, BZ) 
(q0, 1, B) = (q1, B) 
(q1, 2, B) = (q2, λ) 
(q2, 2, B) = (q2, λ) 
 
d. 
 
 
e. 
 
 
Inicial = q0 
Final q2 
(q0, 0, λ) = (q0, a) 
(q0, 1, a) = (q1, λ) 
(q1, 1, a) = (q1, λ) 
(q1, λ, z) = (q2, x) 
 
Inicial = q0 
Final q1 
(q0, 1, λ) = (q0,1) 
(q0, 0, 1) = (q1, λ) 
(q1, 0, 1) = (q1, λ) 
 
 
Con el ejercicio seleccionado debe diligenciar la siguiente tabla: 
 
EJERCICIO A 
TRABAJAR 
 
Registre aquí el Ejercicio a trabajar. Por favor 
agregue la imagen 
Caracterización 
del autómata a 
pila 
En este espacio se realiza: 
- Mediante la definición formal explicar las 
características del autómata, identificación de la 
séptupla. 
 
 
5 
 
- Realizar la tabla de transición 
- Realizar un cuadro comparativo de la 
Equivalencia entre AP por vaciado de pila y AP 
por estado final 
 
Procedimiento 
de paso a paso 
del recorrido 
de una cadena 
Realice de manera detallada y grafica el 
procedimiento paso a paso del recorrido de una 
cadena (La cadena la selecciona el estudiante, 
debe contener como mínimo 5 caracteres) en el 
autómata a pila. Describir cómo funciona el 
almacenamiento en la pila, como funciona LIFO, 
etc. 
 
- Paso 1… 
- Paso 2… 
- Paso 3… 
 
Ejemplo: 
 
Gráfico 
 
Realizar la representación utilizando flechas, 
conexiones, diagramas que permitan ver el 
funcionamiento del autómata a pila 
 
Para una transición: 
F (q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)} 
 
- Paso 1: cuando el autómata se encuentra en el 
estado q, lee el símbolo de entrada a y tiene el 
símbolo A en la cima de la pila. 
 
 
6 
 
- Paso 2: El autómata pasará a algún estado q1, 
eliminará el símbolo A de la pila e introducirá en 
ella la palabra Zi, quedando la cabeza de Zi en la 
cima de la pila. 
- Paso 3: El procedimiento se repite n veces 
 
Practicar y 
verificar lo 
aprendido 
Apoyándose en el simulador JFlap (Anexo 1 - JFLAP) o 
VAS (Anexo 2- VAS) ejecutar y validar por lo menos 
cinco cadenas válidas y 5 cadenas rechazadas por el 
autómata. En este espacio adjunta la imagen. 
 
Lenguaje 
regular 
Agregar el lenguaje regular del autómata 
 
Ejercicios 2: Gramática del autómata 
 
El estudiante realiza paso a paso la gramática del autómata que 
seleccionó. 
 
Identifique su gramática (de forma manual) por la derecha o izquierda y 
la caracteriza.Debe incluir el diagrama de estados con los componentes 
de la gramática asociados a las variables y a las constantes. 
 
Ejercicio Grupal: Minimización de autómatas 
 
Teniendo en cuenta la siguiente tabla de transiciones cree el autómata y 
realice el proceso de minimización paso a paso. 
 
Estados a b 
-> q0 q1 q2 
q1 q3 q5 
q2 q6 q4 
q3 q3 q5 
q4 q6 q4 
q5 q6 q4 
# q6 q3 q5 
 
 
 
7 
 
Deben diligenciar la siguiente información: 
 
EJERCICIO A 
TRABAJAR 
 
Registre aquí el Ejercicio a trabajar. Por favor 
agregue la imagen 
Procedimiento 
de 
minimización 
Realice de manera detallada el procedimiento paso 
a paso de la minimización del autómata. 
 
- Paso 1… 
- Paso 2… 
- Paso 3… 
 
Resultado del 
Autómata 
minimizado 
 
Agregue aquí la imagen del autómata minimizado 
 
Notación 
formal del 
autómata 
minimizado 
 
En este espacio agrega la notación formal del 
autómata. Identifique la quíntupla del autómata 
minimizado. 
Realice la tabla de transición 
 
Caracterización 
del autómata 
parte teórica 
Identifique los elementos (tupla, estado final, inicial, 
alfabeto, etc.). Debe explicar y describir cada 
elemento y la función y significado en el autómata. 
Conceptos y definiciones adicionales. 
 
 Lenguaje 
Regular 
En este espacio agrega el lenguaje regular del 
autómata. 
 
 Gramática del 
autómata 
En este espacio agrega la gramática del autómata. 
Identifique su gramática (de forma manual) por la 
derecha y caracterícela. Debe incluir el diagrama de 
estados con los componentes de la gramática 
asociados a las variables y a las constantes. 
Validación de 
cadenas 
- Identifique 5 cadenas aceptadas y cinco cadenas 
rechazadas 
 
 
 
8 
 
Practicar y 
verificar lo 
aprendido 
Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o 
VAS (Anexo 2- VAS) (gráficamente) como recorre una 
cadena válida. Explique cada secuencia. (No se trata 
solo de captura las imágenes, estas deben ser 
explicadas en pie de página o de lo contrario no tienen 
validez) 
 
 
 
Para el desarrollo de la actividad tenga en cuenta que: 
 
En el entorno de Aprendizaje Unidad 2 debe: Consultar el material 
bibliográfico de la segunda unidad del curso. 
 
En el entorno de Aprendizaje debe: Interactuar en el foro para la Tarea 
3 presentando los avances de sus ejercicios. 
 
En el entorno de Evaluación debe: Entregar el trabajo por parte del 
estudiante seleccionado con el desarrollo de la actividad según los 
estudiantes que hayan participado. 
 
Evidencias de trabajo independiente: 
Las evidencias de trabajo independiente para entregar son: 
 
Desarrollo de cada uno de los ejercicios seleccionados en la Tabla de 
selección de ejercicios; los cuales debe entregar en formato Pdf y 
presentar en el foro habilitado para la Tarea 3 que se encuentra en el 
Entorno de Aprendizaje. 
 
Entregar el trabajo: Cada estudiante debe entregar en el foro el desarrollo 
de sus ejercicios en un documento Pdf con los siguientes elementos: 
• Portada. 
• Desarrollo de los ejercicios 
• Referencias Bibliográficas en normas APA. 
• El nombre del archivo debe ser 301405_(cédula). 
 
Evidencias de trabajo grupal: 
 Las evidencias de trabajo grupal a entregar son: 
 
 
 
9 
 
Presentar en el mismo foro, por lo menos dos aportes significativos a la 
solución del ejercicio para desarrollo grupal. 
 
Desarrollo del ejercicio planteado como ejercicio grupal, 
 
Consolidar y entregar el trabajo: Los estudiantes que participen en el foro 
con aportes deben consolidar el trabajo colaborativo en un documento 
Pdf con los siguientes elementos: 
• Portada. 
• Desarrollo del ejercicio 
• Referencias Bibliográficas en normas APA. 
 
El estudiante que tiene el rol de entrega del grupo lo debe entregar en el 
Entorno de Evaluación en formato pdf y el nombre del archivo debe ser 
301405_ (número del grupo). 
 
El estudiante que entrega el trabajo grupal debe hacer un archivo .zip 
donde estará su entrega individual y la grupal, el nombre del archivo debe 
ser 301405_Final (número del grupo) 
 
 
 
10 
 
2. Lineamientos generales para la elaboración de las evidencias 
de aprendizaje a entregar. 
Para evidencias elaboradas en grupo colaborativamente, tenga en 
cuenta las siguientes orientaciones 
 
1. Todos los integrantes del grupo deben participar con sus aportes 
en el desarrollo de la actividad. 
2. En cada grupo deben elegir un solo integrante que se encargará 
de entregar el producto solicitado en el entorno que haya señalado 
el docente. 
3. Antes de entregar el producto solicitado deben revisar que cumpla 
con todos los requerimientos que se señalaron en esta guía de 
actividades. 
4. Solo se deben incluir como autores del producto entregado, a los 
integrantes del grupo que hayan participado con aportes durante 
el tiempo destinado para la actividad. 
 
Tenga en cuenta que todos los productos escritos individuales o 
grupales deben cumplir con las normas de ortografía y con las 
condiciones de presentación que se hayan definido. 
En cuanto al uso de referencias considere que el producto de esta 
actividad debe cumplir con las normas APA 
En cualquier caso, cumpla con las normas de referenciación y evite el 
plagio académico, para ello puede apoyarse revisando sus productos 
escritos mediante la herramienta Turnitin que encuentra en el campus 
virtual. 
 
Considere que en el acuerdo 029 del 13 de diciembre de 2013, artículo 
99, se considera como faltas que atentan contra el orden académico, 
entre otras, las siguientes: literal e) “El plagiar, es decir, presentar como 
de su propia autoría la totalidad o parte de una obra, trabajo, 
documento o invención realizado por otra persona. Implica también el 
uso de citas o referencias faltas, o proponer citad donde no haya 
coincidencia entre ella y la referencia” y liberal f) “El reproducir, o copiar 
con fines de lucro, materiales educativos o resultados de productos de 
investigación, que cuentan con derechos intelectuales reservados para 
la Universidad” 
 
 
 
11 
 
Las sanciones académicas a las que se enfrentará el estudiante son las 
siguientes: 
a) En los casos de fraude académico demostrado en el trabajo 
académico o evaluación respectiva, la calificación que se impondrá será 
de cero puntos sin perjuicio de la sanción disciplinaria correspondiente. 
b) En los casos relacionados con plagio demostrado en el trabajo 
académico cualquiera sea su naturaleza, la calificación que se impondrá 
será de cero puntos, sin perjuicio de la sanción disciplinaria 
correspondiente. 
 
 
 
 
12 
 
3. Formato de Rúbrica de evaluación 
Tipo de actividad: Independiente 
Momento de la evaluación: Intermedio 
La máxima puntuación posible es de 115 puntos 
Primer criterio de 
evaluación: 
Contenido 
Procedimiento 
Construye un 
autómata de pila - 
Desarrolla y explica 
paso a paso el 
ejercicio propuesto de 
autómata de pila. 
Este criterio 
representa 40 
puntos del total 
de 115 puntos de 
la actividad. 
 
Nivel alto: El estudiante diseña y construye el autómata de pila, y 
explica paso a paso el ejercicio propuesto y soluciona de manera 
correcta los puntos solicitados. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 34 puntos y 40 puntos 
 
Nivel Medio: El estudiante diseña y construye el autómata de pila, 
pero no explica paso a paso el ejercicio propuesto o no soluciona de 
manera correcta o completa los puntos solicitados. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 24 puntos y 33 puntos 
 
Nivel bajo: El estudiante no diseña ni construye el autómata de pila, 
o no explica paso a paso el ejercicio propuesto o no soluciona de 
manera correcta los puntos solicitados. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 0 puntos y 23 puntos 
 
Segundo criterio 
de evaluación: 
Contenido 
Procedimiento 
Construye gramáticas 
regulares – Realiza 
ejercicio paso a paso 
de gramática regularEste criterio 
representa 30 
puntos del total 
de 115 puntos de 
la actividad 
 
Nivel alto: El estudiante construye la gramática regular, realizando el 
paso a paso y resuelve los puntos solicitados de manera correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 25 puntos y 30 puntos 
 
Nivel Medio: El estudiante construye la gramática regular, pero no 
realiza el paso a paso o no resuelve los puntos solicitados de manera 
correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 18 puntos y 24 puntos 
 
Nivel bajo: El estudiante no construye la gramática regular, o no 
realiza el paso a paso o no resuelve los puntos solicitados de manera 
correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 0 puntos y 17 puntos 
 
 
 
13 
 
 
 
 
 
 
 
 
 
Tercer criterio de 
evaluación: 
Procedimiento 
Desarrolla y explica 
paso a paso el 
ejercicio propuesto de 
minimización de 
autómatas y realiza la 
gramática regular. 
Este criterio 
representa 45 
puntos del total 
de 115 puntos de 
la actividad 
Nivel alto: El estudiante realiza la situación planteada de 
minimización de autómatas, realiza el ejercicio paso a paso de manera 
correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 38 puntos y 45 puntos 
 
Nivel Medio: El estudiante realiza la situación planteada de 
minimización de autómatas, pero no realiza el ejercicio paso a paso de 
manera correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 27 puntos y 37 puntos 
 
Nivel bajo: El estudiante no realiza la situación planteada de 
minimización de autómatas, o no realiza el ejercicio paso a paso de 
manera correcta. 
Si su trabajo se encuentra en este nivel puede obtener 
entre 0 puntos y 26 puntos