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

...