Programa del curso: Automata y lenguajes formales

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

Escuela de Ciencias Básicas, Tecnología e Ingeniería

Curso: Autómatas y lenguajes Formales. 301405. Ing. (Msc). Carlos Alberto Amaya Tarazona

GUIA ACTIVIDADES - EJERCICIO A DESARROLLAR PARA MOMENTO 2 2015-1

Autómatas y lenguajes Formales_ 301405

Producto del momento dos: 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) se deben realizar o “recrear” 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. En las siguientes direcciones de Internet podrán descargar las mencionadas herramientas: • O EN EL MODULO DEL AULA (Ver 4 – 2014 -2) EN LA PAGINA 155 ENCUENTRAN TODA LA LISTA DE HERRAMIENTAS Y LAS URLS DE DESCARGA.

Visual Autómata Simulator. http://www.cs.usfca.edu/~jbovet/vas.html

JFLAP. http://www.cs.duke.edu/csed/jflap/

DOCUMENTO A ENTREGAR: Se debe entregar un archive comprimido (.rar) que contenga el siguiente nombre: Como ejemplo, si el grupo es el 44, entonces el archivo a enviar es: 44_mom2_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 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.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

Escuela de Ciencias Básicas, Tecnología e Ingeniería

Curso: Autómatas y lenguajes Formales. 301405. Ing. (Msc). Carlos Alberto Amaya Tarazona

No se está solicitando introducción, objetivos, bibliografía. Lo importante de esta actividad es estar concentrados en el desarrollo del ejercicio como estrategia de Problemas. Estos no son considerados como aportes ni deben ir plasmados en el trabajo.

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:

PARTE 1: Calcular el autómata mínimo correspondiente al siguiente autómata finito.

1. Enuncie el autómata en notación matemática

2. Identifique los componentes del autómata (que tipo de tupla es)

3. Identifique la tabla de transición correspondiente

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que terminen en un estado “halt”

5. Encuentre la expresión regular válida.

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha (eso significa que debe hacerla por ambos lados y verificar cual es válida sustentando el por qué). Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

7. Realice el árbol de Derivación de esa gramática

8. Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su afirmación

9. Si el árbol de transición es demasiado grande, a su criterio seleccione una regla en la que se detenga por cualquier rama (izquierda o derecha) y plásmelo hasta ahí. (es decir seleccione una cadena válida para este ítem).

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

Escuela de Ciencias Básicas, Tecnología e Ingeniería

Curso: Autómatas y lenguajes Formales. 301405. Ing. (Msc). Carlos Alberto Amaya Tarazona

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR O YA MINIMIZADO:

1. Explicar el proceso de Minimización (que estados se suprimen y porque). Realice la tabla de estados distinguibles.

2. Que transiciones se reemplazan o resultan equivalentes

3. Escribir la función de transición del nuevo autómata.

4. Identificar la expresión regular (explicarla en la lectura matemática que se le debe hacer).

5. Compruebe una cadena válida para esa expresión regular.

6. Identificar el lenguaje que reconoce y cinco posibles cadenas válidas

7. Identificar su gramática. Demuéstrela para una cadena válida del autómata.

8. Compare la gramática con el autómata antes de minimizar (ya sea por la izquierda o derecha).

9. El autómatas nuevo expresarlo o graficarlo con su respectivo diagrama de Moore.

10. Identificar sus tablas de Transición (plasmarlas)

11. Plasmar los pasos de minimización en el simulador (compárelos con el proceso manual que está explicando) y capturar los procesos en imágenes para ser documentadas en el texto.

PARTE 2: Diseñe un APD que acepte cadenas de este tipo (con pila vacía): {(abc) (aabcc) (aaabccc) (aaaabcccc) (aabccccc) ( abccccc) (aabcccc) (aaaaaabcccccccccc) (aaabccccc) (aaabccccccccccc)}

Cadenas no válidas. {(bcc) (ac) (aabc9 (aaaabcc) (aaaccccb) (acb) (aaaaabcc) (aaabcc)}

1. Describa el autómata en notación matemática, y ncuentre en primera instancia una regla que evalúe estas cadenas y que cumpla las condiciones de las mismas.

2. Grafíquelo en JFLAP y realice el “Traceback” para las transiciones. (Las columnas para un AP son: El estado en que se encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de la pila).

3. Plasme las imágenes y capturas en el documento. (Documente el proceso)

4. Muestre el diagrama correspondiente de estados.

5. Identifique los contenidos (el recorrido para cada interacción) de la pila y el estado de parada. Realícelo con una cadena válida.

Consideraciones generales:

No se calificará el informe que no sea montado en el espacio indicado.

· El archivo debe colgarse en el espacio dentro del foro momento cuatro, en el entorno de aprendizaje colaborativo, llamado: “Desarrollo y envío del trabajo del momento cuatro”, antes de la fecha de cierre, según lo indicado en la agenda del curso.

· El tamaño del archivo no debe superar 2Mb.

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.

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. 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

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

Escuela de Ciencias Básicas, Tecnología e Ingeniería

Curso: Autómatas y lenguajes Formales. 301405. Ing. (Msc). Carlos Alberto Amaya Tarazona

 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.

“Lo importante no es el tiempo, lo importante es lo que se hace con él”

...