GUIA_COL1_301405_2014-I

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas Tecnología e Ingeniería. Ingeniería de Sistemas AUTÓMATAS LENGUAJES FORMALES. Ing. (Msc). Carlos Alberto Amaya Tarazona

AUTOMATAS Y LENGUAJES FORMALES

301405

Programa: Ingeniería de Sistemas

GUIA DE ACTIVIDAD

TRABAJO COLABORATIVO N 1

LENGUAJES REGULARES

DUITAMA

ENERO DE 2014


Temáticas revisadas:

Primera Unidad Capítulos Lecciones

I.. LENGUAJES REGULARES

1. Conceptos Básicos 1. Introducción e Historia.

2. Diferentes Modelos de Computación

3. Autómatas y Lenguajes.

4. Lenguajes Regulares

5. Autómata

2. Autómatas Finitos 6. Definición Formal de Autómatas Finitos

7. Autómatas Finitos Determinísticos (AFD)

8. Autómatas Finitos no Determinísticos (AFND)

9. Autómatas Finitos con λ Transacciones

10. Lenguaje Aceptado por Autómata Finito

3. Expresiones Regulares 11.Expresiones Regulares

12. Significado de las Expresiones Regulares

13. Autómatas Finitos y Expresiones Regulares

14.Propiedades de los Lenguajes Regulares

15.Equivalencia de Autómatas Finitos Determinísticos y Autómatas Finitos

Los lenguajes pueden describirse como elementos que se generan, como cadenas a partir de cadenas sencillas, con el uso de operaciones de cadenas o el desarrollo del lenguaje mismo, que se puede generar con otros lenguajes más sencillos mediante operaciones de conjuntos. Los Lenguajes más sencillos son los considerados lenguajes regulares, es decir, los que se pueden generar a partir de lenguajes de un elemento con la aplicación de ciertas operaciones estándar realizadas un número finito de veces. Estos son pues los lenguajes que pueden reconocer los dispositivos llamados Autómatas finitos (AF) que son máquinas de cómputo con memoria muy restringida. En esta unidad se considera como segundo aspecto la idea de que un lenguaje no sea regular, además de proporcionar un modelo sencillo de computación que se puede generalizar en las unidades siguientes. Con las caracterizaciones anteriores y otras de los lenguajes regulares se obtienen y estudian algoritmos para traducir una descripción de un lenguaje a otra descripción de un tipo distinto; se acumula experiencia en el uso de métodos formales para describir lenguajes y se intenta responder a preguntas acerca de ellos, son preguntas y ejercicios sencillos con sus respuestas y que permiten determinar la utilidad de los lenguajes regulares en aplicaciones del mundo real.


OBJETIVO GENERAL: Reconocer los lenguajes regulares, autómatas finitos y su aplicación. OBJETIVOS ESPECIFICOS Estudiar la aplicación de los lenguajes regulares y los autómatas finitos. Adquirir las habilidades necesarias para desarrollar autómatas y máquinas que reconozcan lenguajes o computen funciones. Distinguir los diferentes tipos de lenguajes formales existentes. Adquirir el conocimiento y competencia para poder recrear autómatas sencillos en un simulador. De igual forma verificar el lenguaje que reconoce. METODOLOGÍA: Las sesiones son desarrolladas en forma teórica, La estrategia de aprendizaje a utilizar será el Aprendizaje colaborativo. Porque aprendizaje colaborativo? El desarrollo de las actividades de aprendizaje está basado en el aprendizaje colaborativo como una estrategia de aprendizaje y de trabajo de grupo que es usado en los cursos que se ofertan en el campus virtual de la UNAD, se requieren estas características para realizar un trabajo realmente efectivo. Participación: el potencial de un grupo de aprendizaje se maximiza cuando todos los estudiantes participan activamente en las discusiones. Crecimiento Social: permite establecer y mantener una comprensión compartida de significados. Habilidades Conversacionales: la calidad de la comunicación en grupos de discusión influencia la experiencia de aprendizaje y los logros de los miembros del grupo. Procesamiento Grupal y Análisis de Rendimiento: existe procesamiento grupal cuando el grupo discute sus progresos y decide si continúa con su comportamiento o lo cambia. Para ello los estudiantes deben evaluar individual y colectivamente sus rendimientos. Formación de los grupos colaborativos: Los Grupos están conformados por 5 estudiantes que el sistema en el momento del ingreso al curso académico los selecciona, es de anotar que este grupo está definido para desarrollar todo el curso académico y no es factible el cambio de grupo, este proceso fomenta deliberadamente la diversidad mezclando los estudiantes con diferente nivel, sexo, origen, estilo de aprendizaje, etc. Aunque esta distribución no toma en cuenta la opinión de cada estudiante si pretende que se conserve dentro del equipo la pluralidad para potenciar la calidad, la cantidad y la velocidad de aprendizaje.


Organización los Grupos colaborativos: Los equipos luego de la distribución aleatoria que hace el sistema deben organizarse en este pequeño grupo obviamente con el compromiso de trabajar y de desempeñar algunos roles o funciones básicas, que son indispensables para el desarrollo de la actividad. Una distribución de funciones básicas que se propone y debe ser definida una vez se hayan “conocido” los integrantes del grupo, es la siguiente (coordinador, relator, animador, técnico y supervisor) aunque los estudiantes pueden crear las funciones que consideren más adecuadas. En cada unidad de aprendizaje del curso los estudiantes deben elegir un coordinador del equipo que, a su vez, distribuye el resto de funciones entre sus compañeros. Cuando comienza una nueva unidad deben volver a elegir un coordinador pero de tal forma que nadie repita un cargo hasta que todos han pasado ya por ese cargo. La idea es que todos aprendan a ser responsables de todas las funciones esenciales dentro de un equipo, que todos vivan la experiencia de esa responsabilidad. ¿Cómo se logra pertenencia con el grupo colaborativo?: Lo importante en la conformación del equipo es el hecho de que se sientan parte del equipo en el cual van a trabajar durante todo el semestre, para ello cada grupo deberá ponerse de acuerdo para desarrollar una primera actividad grupal, que está planteada en el foro general del curso, deberán elaborar una presentación multimedia que debe contener un acta de conformación del grupo, un nombre para el equipo, un logo distintivo del grupo y la redacción de texto en donde el equipo se presenta a sus compañeros explicando sus puntos fuertes y débiles. ¿Cómo organizar su trabajo?: En este punto cobra relevancia e importancia el uso del wiki como elemento para compartir toda la información del grupo y registrar los aportes de cada uno de los integrantes del grupo, si es decisión del grupo no usar el wiki, pueden realizar sus aporte por el foro colaborativo de cada práctica en los temas de trabajo individual y trabajo grupal. Producto esperado a entregar: 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, ( 4, 5 y 10) 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. Importante:


Tenga en cuenta que no se aceptan fórmulas, caracteres o expresiones regulares, entre otros que sean copiadas como imagen. 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 EN LA PAGINA 154 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 estudiante se llama Carlos Alberto Amaya Tarazona y pertenece al grupo 27, entonces el archivo a enviar es: 27_col1_301405.rar

El archivo comprimido contendrá los siguientes elementos:

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

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

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

Éxitos. Cordialmente. Ing. (Msc) Carlos Alberto Amaya Tarazona Director aula.

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


EJERCICIO A DESARROLLAR: PARTE 1: Dada la siguiente tabla de transición:

(Nótese que hay interacciones con símbolo vacío, diferente a cadena vacía)

1. Exprese el autómata en notación matemática. Identifique que tipo de

autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el

concepto de determinismo)

2. Identifique los elementos (tupla que es). Debe explicar y describir cada

elemento y la función y significado en el autómata. Conceptos y

definiciones adicionales.

3. Identifique el lenguaje que genera.

4. Muestre en el simulador (gráficamente) como recorre una cadena válida.

Explique cada secuencia.

5. Muestre el diagrama de Moore generado en JFLAp y en VAS y comente

que similitudes o diferencias encuentra al realizarlo en los dos simuladores.

(herramientas que ofrezca uno u otro).

PARTE 2: Para cada una de las Expresiones Regulares siguientes (ER) realice:

6. Identifique el lenguaje que representa: (tenga en cuenta como se plasma o

identifica un lenguaje aceptado: módulo página 47 lección 10)

7. Genere tres cadenas válidas y dos no válidas

8. Plasme las tres cadenas válidas para cada ER en una tabla (identificando

jerarquía de operadores regulares, identificando colores). Para ello

apóyese en el video: http://youtu.be/JZPAHHA2PnE (minuto 14 al 33)

9. Identifique en la misma tabla por que las dos cadenas seleccionadas no se

aceptan o en que parte se trunca la jerarquía y orden de los operadores.

10. Seleccione una ER (solo una) y expórtela o genere el autómata o el

diagrama de Moore que sea válido.

http://youtu.be/JZPAHHA2PnE


EXPRESIONES REGULARES:

Primera: (a+b)*b(b+a)b(b+a)*

Segunda: (0+1)*11(1+0)0(1+10*)*

Tercera: 0*1*+(01)*+(11*00*+01)

Cuarta: Una ER libre (la que desee construir)

Quinta: la ER de la tabla de transición del autómata de la Parte 1.

Documents

GUIA_COL1_301405_2014-I