1. No category

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Curso: Autómatas y lenguajes Formales - 301405
GUIA ACTIVIDADES - EJERCICIO A DESARROLLAR PARA MOMENTO 1
PERIODO 8 – 03
Autómatas y Lenguajes Formales_ 301405
Producto del momento uno: El producto es un documento que debe cubrir todos los puntos de la rúbrica de
evaluación y debe ser elaborado en un procesador de palabras (Openoffice Write o Microsoft Word.) para luego
ser convertido a PDF (Portable data File).
NOTA IMPORTANTE. Para los ejercicios propuestos de esta actividad, (que son dos) puede apoyarse o
“recrearlos” en alguno de los dos simuladores: Los gráficos y análisis de cada simulador son los que se
exportaran al documento de Word. Debe entregar los archivos generados por el simulador en una carpeta.
Tenga en cuenta que no se aceptan fórmulas, caracteres o expresiones regulares, entre otros que sean
copiadas como imagen (Incluso las imágenes propias de esta guía). Se debe usar un editor de fórmulas para
plasmarlas. Los gráficos deben ser generados por simuladores o si los realiza en un editor de gráficos
manualmente, también son aceptados.
El Visual Autómata Simulator (vas) y/o el JFLAP. Los pueden descargar desde el entorno de aprendizaje
práctico
Visual Autómata Simulator.
http://datateca.unad.edu.co/contenidos/301405/2015_1/SIMULADORES/VISUAL_AUTOMATA_SIM
ULATOR.zip
JFLAP.
http://datateca.unad.edu.co/contenidos/301405/2015_1/SIMULADORES/JFLAP.zip
DOCUMENTO A ENTREGAR: Se debe entregar un archivo comprimido (.rar) que contenga el siguiente
nombre: Como ejemplo, si el grupo es el 44, entonces el archivo a enviar es: 44_mom1_301405.rar
EL ESPACIO ASIGNADO PARA QUE CARGUE O ENTREGUE LE ACTIVIDAD ES EN EL “ENTORNO
DE EVALUACION Y SEGUIMIENTO”
El archivo comprimido contendrá los siguientes elementos:
UN DOCUMENTO EN PDF: que contiene: Formato de presentación del Documento: El documento debe
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Curso: Autómatas y lenguajes Formales - 301405
contener los siguientes puntos
PORTADA: Datos de los Estudiantes (nombre, número de matrícula, e-mail, Zona, Cead, Grupo que
presenta la actividad). Datos del tutor. Descripción general del trabajo. Desarrollo de cada uno de los
puntos enunciados a continuación.
LOS ARCHIVOS GENERADOS POR EL SIMULADOR EN UNA CARPETA: Si es JFLAP (los de
extensión jff) y si es con archivos de VAS (los de extensión .fa)
Problemas a desarrollar:
1. Las expresiones regulares (ER), pueden también escribirse de otras formas o con otra secuencia de
operadores o distribución de símbolos. En general es una forma matemática que representa el Lenguaje
que genera un Autómata. Y esas expresiones regulares siempre serán válidas siempre y cuando
representen exactamente el mismo lenguaje para un Autómata. Concluyendo, para un Autómata,
puede haber más de una ER que representa el mismo lenguaje ya sea que esa ER sea minimizada,
extensa, equivalente o como se prefiera escribir. Solo que en los diseños óptimos computacionales siempre
se buscará la mejor ER (corta o mínima) para efectos de la mejor simulación o para llevarlas a lenguajes de
programación en la creación de soluciones computacionales (solucionar problemas - Algoritmos)
Dados los siguientes ítem, Autómatas Finitos Deterministas, Autómatas Finitos no Deterministas, lenguajes
y expresiones regulares (ER), encuentre según corresponda:
AFN / AFD
LENGUAJE
EXPRESIÓN
REGULAR
EJ1
EJ2
EJ3
L= { cadenas que empiezan por a y no
tienen dos ceros (0) consecutivos}
2. PARA LA EXPRESION REGULAR : c*a+c*a(a+b+cc*b)*
SIMPLIFIQUE LA EXPRESIÓN REGULAR Y RESUELVA:
1. Describa la forma matemática del autómata,
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Curso: Autómatas y lenguajes Formales - 301405
2. Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y
justifique su respuesta. (No se trata de dar el concepto de determinismo sino de justificarlo
asociando la respuesta al diseño del autómata)
3. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del
ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en
el autómata. Conceptos y definiciones adicionales.
4. Identifique el lenguaje que genera.
5. Muestre en el simulador (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 pié
de página o de lo contrario no tienen validez)
6. Muestre el diagrama de Moore generado en JFLAP y en VAS y comente tres similitudes y
tres diferencias que encuentra al realizarlo en los dos simuladores. (herramientas que
ofrezca uno u otro).
7. Genere tres cadenas válidas y dos no válidas.
3. Teniendo en cuenta el siguiente autómata identifique si es AFD o AFND, Si es un AFD genere un
AFND que reconozca el mismo lenguaje; o por lo contrario si el autómata inicial es un AFND, genere
un AFD que reconozca el mismo lenguaje.
1. Describa la forma matemática del autómata
2. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del
ejercicio propuesto).
3. Muestre en el simulador (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 pié
de página o de lo contrario no tienen validez)
4. Muestre el diagrama de Moore generado en JFLAP y en VAS
5. Identifique la ER asociada al nuevo diseño y compárela con la expresión regular
simplificada (es decir analícelas con dos cadenas válidas y con dos no válidas). Para ello
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Curso: Autómatas y lenguajes Formales - 301405
debe identificar en una tabla la jerarquía de operadores regulares, identificando con
colores las sentencias matemáticas.
Consideraciones generales:
No se calificará el informe que no sea montado en el espacio indicado.
Recuerde que el Foro es el espacio adecuado para construir y desarrollar el trabajo de forma colaborativa, la
clave es la planificación, organización y compromiso del equipo de trabajo. Revisen los aportes para la
consolidación de los trabajos en cuanto a si están correctos y caracterizados de acuerdo a lo solicitado. Puede
solicitar revisiones previas de su avance de trabajo o aportes antes de consolidar, formulando sus inquietudes
en el espacio de “dudas e inquietudes”
El estudiante que no participe en el foro de trabajo colaborativo durante el período establecido en la agenda del
curso, obtendrá una nota de 0 en esta actividad (Téngase en cuenta que los aportes realizados dos días
antes del cierre de la actividad, no se tendrán en cuenta). No se aceptan como aportes o insumos,
enunciados o mensajes que solo digan o expresen intenciones de trabajar.
El plagio tiene una calificación de 0 en la actividad.
Recomendaciones
 Leer cuidadosamente las indicaciones registradas en los foros (noticias del curso, foro general, foro del
trabajo colaborativo), por parte del director(a), para el adecuado desarrollo de los diferentes momentos
diseñados.
 Consultar con su tutor(a), cada vez que lo requiera, para aclarar dudas e inquietudes que se presenten
en el proceso.
 Avanzar con el desarrollo de las actividades solicitadas en cada uno de los momentos de acuerdo a las
fechas registradas en la agenda.