guia_col1_2013_i
TRANSCRIPT
-
7/28/2019 guia_col1_2013_I
1/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
AUTOMATAS Y LENGUAJES FORMALES
301405
Programa: Ingeniera de Sistemas
GUIA DE ACTIVIDAD
TRABAJO COLABORATIVO N 1
LENGUAJES REGULARES
DUITAMA
ENERO DE 2013
-
7/28/2019 guia_col1_2013_I
2/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
Temticas revisadas:
Primera Unidad Captulos LeccionesI.. LENGUAJESREGULARES
1. Conceptos Bsicos 1. Introduccin e Historia.2. Diferentes Modelos de Computacin3. Autmatas y Lenguajes.4. Lenguajes Regulares5. Autmata
2. Autmatas Finitos 6. Definicin Formal de AutmatasFinitos7. Autmatas Finitos Determinsticos(AFD)8. Autmatas Finitos no Determinsticos(AFND)9. Autmatas Finitos con Transacciones10. Lenguaje Aceptado por AutmataFinito
3. Expresiones Regulares 11.Expresiones Regulares12. Significado de las ExpresionesRegulares13. Autmatas Finitos y ExpresionesRegulares14.Propiedades de los LenguajesRegulares15.Equivalencia de Autmatas FinitosDeterminsticos y Autmatas Finitos
Los lenguajes pueden describirse como elementos que se generan, como cadenasa partir de cadenas sencillas, con el uso de operaciones de cadenas o eldesarrollo del lenguaje mismo, que se puede generar con otros lenguajes mssencillos mediante operaciones de conjuntos.
Los Lenguajes ms sencillos son los considerados lenguajes regulares, es decir,los que se pueden generar a partir de lenguajes de un elemento con la aplicacinde ciertas operaciones estndar realizadas un nmero finito de veces.
Estos son pues los lenguajes que pueden reconocer los dispositivos llamadosAutmatas finitos (AF) que son mquinas de cmputo con memoria muyrestringida. En esta unidad se considera como segundo aspecto la idea de que unlenguaje no sea regular, adems de proporcionar un modelo sencillo de
computacin que se puede generalizar en las unidades siguientes.
Con las caracterizaciones anteriores y otras de los lenguajes regulares seobtienen y estudian algoritmos para traducir una descripcin de un lenguaje a otradescripcin de un tipo distinto; se acumula experiencia en el uso de mtodosformales para describir lenguajes y se intenta responder a preguntas acerca deellos, son preguntas y ejercicios sencillos con sus respuestas y que permitendeterminar la utilidad de los lenguajes regulares en aplicaciones del mundo real.
-
7/28/2019 guia_col1_2013_I
3/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
OBJETIVO GENERAL:Reconocer los lenguajes regulares, autmatas finitos y su aplicacin.
OBJETIVOS ESPECIFICOSEstudiar la aplicacin de los lenguajes regulares y los autmatas finitos.
Adquirir las habilidades necesarias para desarrollar autmatas y mquinas quereconozcan lenguajes o computen funciones.Distinguir los diferentes tipos de lenguajes formales existentes.
Adquirir el conocimiento y competencia para poder recrear autmatas sencillos enun simulador. De igual forma verificar el lenguaje que reconoce.
METODOLOGA: Las sesiones son desarrolladas en forma terica, La estrategiade aprendizaje a utilizar ser el Aprendizaje colaborativo.
Porque aprendizaje colaborativo?
El desarrollo de las actividades de aprendizaje est basado en el aprendizajecolaborativo como una estrategia de aprendizaje y de trabajo de grupo que esusado en los cursos que se ofertan en el campus virtual de la UNAD, se requierenestas caractersticas para realizar un trabajo realmente efectivo. Participacin: elpotencial de un grupo de aprendizaje se maximiza cuando todos los estudiantesparticipan activamente en las discusiones.
Crecimiento Social: permite establecer y mantener una comprensin compartidade significados.
Habilidades Conversacionales: la calidad de la comunicacin en grupos dediscusin influencia la experiencia de aprendizaje y los logros de los miembros delgrupo.
Procesamiento Grupal y Anlisis de Rendimiento: existe procesamiento grupalcuando el grupo discute sus progresos y decide si contina con sucomportamiento o lo cambia. Para ello los estudiantes deben evaluar individual ycolectivamente sus rendimientos.
Formacin de los grupos colaborativos: Los Grupos estn conformados por 5
estudiantes que el sistema en el momento del ingreso al curso acadmico losselecciona, es de anotar que este grupo est definido para desarrollar todo elcurso acadmico y no es factible el cambio de grupo, este proceso fomentadeliberadamente la diversidad mezclando los estudiantes con diferente nivel, sexo,origen, estilo de aprendizaje, etc. Aunque esta distribucin no toma en cuenta laopinin de cada estudiante si pretende que se conserve dentro del equipo lapluralidad para potenciar la calidad, la cantidad y la velocidad de aprendizaje.
-
7/28/2019 guia_col1_2013_I
4/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
Organizacin los Grupos colaborativos: Los equipos luego de la distribucinaleatoria que hace el sistema deben organizarse en este pequeo grupoobviamente con el compromiso de trabajar y de desempear algunos roles ofunciones bsicas, que son indispensables para el desarrollo de la actividad.
Una distribucin de funciones bsicas que se propone y debe ser definida una vezse hayan conocido los integrantes del grupo, es la siguiente (coordinador, relator,animador, tcnico y supervisor) aunque los estudiantes pueden crear las funcionesque consideren ms adecuadas. En cada unidad de aprendizaje del curso losestudiantes deben elegir un coordinador del equipo que, a su vez, distribuye elresto de funciones entre sus compaeros. Cuando comienza una nueva unidaddeben volver a elegir un coordinador pero de tal forma que nadie repita un cargohasta que todos han pasado ya por ese cargo. La idea es que todos aprendan aser responsables de todas las funciones esenciales dentro de un equipo, quetodos vivan la experiencia de esa responsabilidad.
Cmo se logra pertenencia con el grupo colaborativo?: Lo importante en laconformacin del equipo es el hecho de que se sientan parte del equipo en el cualvan a trabajar durante todo el semestre, para ello cada grupo deber ponerse deacuerdo para desarrollar una primera actividad grupal, que est planteada en elforo general del curso, debern elaborar una presentacin multimedia que debecontener un acta de conformacin del grupo, un nombre para el equipo, un logodistintivo del grupo y la redaccin de texto en donde el equipo se presenta a suscompaeros explicando sus puntos fuertes y dbiles.
Cmo organizar su trabajo?: En este punto cobra relevancia e importancia el
uso del wiki como elemento para compartir toda la informacin del grupo yregistrar los aportes de cada uno de los integrantes del grupo, si es decisin delgrupo no usar el wiki, pueden realizar sus aporte por el foro colaborativo de cadaprctica en los temas de trabajo individual y trabajo grupal.
Para la organizacin del trabajo a desarrollar el proceso es el siguiente:
Planificacin: Se deben repartir las funciones entre los componentes delgrupo colaborativo y planificar el trabajo. Para ello elaboraran un "Plan de
Accin" que es un documento en un procesador de palabras en dondemostrarn el organigrama del equipo, la organizacin del tema en donde se
escriba que saben sobre el tema, que desean aprender y cmo van abuscar la informacin (Desarrollo de la practica en el Cead, BibliotecaVirtual de la UNAD, en la Red, haciendo entrevistas a especialistas, etc.),el diagrama de flujo del proyecto y el calendario de actividades. EsteDocumento debe ser enviado al foro de trabajo colaborativo paracompartirlo con el grupo y con el tutor en el TEMA de produccin del grupo.
-
7/28/2019 guia_col1_2013_I
5/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
Elaboracin del trabajo: Con la informacin individual y grupal recogida enlas bibliotecas, en la Red, haciendo entrevistas a especialistas etc. debernelaborar un informe que recoja lo esencial que han aprendido: el trabajofinal. Para ello negociarn y construirn entre todo el grupo los contenidosde la prctica, se deja la decisin al grupo para que seleccione la tcnica
ms adecuada para compartir la produccin de cada uno, se sugiereelaboren mapas de ideas o un mapa conceptual del tema a partir de lainformacin elaborada individualmente.
Producto esperado a entregar:
El producto es un documento que debe cubrir todos los puntos de la rbrica deevaluacin y debe ser elaborado en un procesador de palabras (openoffice write oMicrosoft Word.) para luego ser convertido a PDF (Portable data File).
NOTA IMPORTANTE. Para los ejercicios propuestos de esta actividad, ( 2 al
10) se deben realizar o recrear en alguno de los dos simuladores: Losgrficos y anlisis de cada simulador son los que se exportaran aldocumento de Word. Debe entregar los archivos generados por el simuladoren una carpeta.
Importante:Tenga en cuenta que no se aceptan frmulas, caracteres o expresionesregulares, entre otros que sean copiadas como imagen. Se debe usar uneditor de frmulas para plasmarlas.
El Visual Autmata Simulator (vas) y/o el JFLAP. En las siguientes direcciones de
Internet podrn descargar las mencionadas herramientas: Visual Autmata Simulator. http://www.cs.usfca.edu/~jbovet/vas.htmlJFLAP.http://www.cs.duke.edu/csed/jflap/
O en el FORO DE NOTICIAS DEL AULA, estn los links de descara directos deforma ms rpida y cmoda.
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 ypertenece al grupo 78, entonces el archivo a enviar es:
78_col1_301405.rar
El archivo comprimido contendr los siguientes elementos:
http://www.cs.duke.edu/csed/jflap/http://www.cs.duke.edu/csed/jflap/http://www.cs.duke.edu/csed/jflap/ -
7/28/2019 guia_col1_2013_I
6/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
1. UN DOCUMENTO EN PDF: que contiene:Formato de presentacin del Documento: El documento debe contener lossiguientes puntos
PORTADA: Datos de los Estudiantes (nombre, nmero de matrcula, e-mail,Zona, Cead, Grupo que presenta la actividad). Datos del tutor.
Descripcin general del trabajo. Desarrollo de cada uno de los puntosenunciados a continuacin..
2. LOS ARCHIVOS GENERADOS POR EL SIMULADOR EN UNACARPETA: Deben incluir los 9 archivos que genera el simulador :(EJERCICIOS 2 AL 9)
Si es JFLAP (los de extensin jff) y si es con archivos de VAS (los deextensin .fa)
Deben asignar nombres a los archivos del simulador as:
Para el ejercicio 2: (as para los dems ejercicios cambiando el nmero)
Ejercicio2.jff (Cuando se usa JFLAP)Ejercicio2.fa (Cuando se usa Visual Autmata Simulator)
xitos.
Cordialmente. Ing. (Msc) Carlos Alberto Amaya TarazonaDirector aula.
-
7/28/2019 guia_col1_2013_I
7/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
DISTRIBUCION DEL TRABAJO
-
7/28/2019 guia_col1_2013_I
8/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
EJERCICIOS A DESARROLLAR:
1. Para el siguiente ejercicio, recordaremos ciertas apreciaciones, conceptos oafirmaciones acerca de las Expresiones Regulares, comnmente denotadascomo ER:
Una expresin regular es una forma de representar cierto tipo de lenguajes sobre
un determinado alfabeto. Son exactamente los aceptados por los autmatas de
estado finito.
Si tomamos como A un alfabeto, unas posibles expresiones regulares sobre ese
alfabeto podran ser: (identifique que lenguaje reconoce esa ER).
a) es una ER que denota el Lenguaje..????
b) es una ER que denota el lenguaje ?En general los lenguajes que pueden representarse mediante una expresinregular se llaman lenguajes regulares. Estos coinciden con los aceptados por losautmatas finitos.
Es importante que tengamos definido o claro que Si r ys son ER denotando loslenguajes R yS, entonces se definen tres operaciones muy bsicas:
- Unin: (r + s) es una expresin regular ER que denota el lenguaje R S- Concatenacin: (rs) algunos autores lo toman como (rs) es una expresin
regular ER que denota le lenguaje RS.
- Clausura: r*
es una expresin regular ER que denota el lenguaje R*
Para efectos de plasmar las ER, los parntesis se pueden eliminar siempre ycuando los smbolos y caracteres no alteren la interpretacin de otros caracteres ocadenas. La precedencia de las operaciones es: clausura / Concatenacin / Unin.
Para los siguientes ejercicios identifique el lenguaje que reconoce y plasme cincoposibles cadenas vlidas que representan esa ER:
EJ EMPLO COMO DEBE REALIZAR EL EJ ERCICIO:Si le dan esta ER (0+1)*011 Quiere decir que representa le lenguaje de las
cadenas que terminan en 011
(Debe evaluar bien lo que va a plasmar de tal forma que no se quede ningunaposibilidad de cadena sin tener en cuenta)
si A = {a,b,c}
c) (a +b)*(a+b)
-
7/28/2019 guia_col1_2013_I
9/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
d) (a* + b ) *
e) (a+ )ba*f) b (aba)*
g) si A = {0,1}
h) 0*+1*(01)
i) 10* + 10
j) 01* + 0
k) (1-11*0) *
l) (1 + 10) + 0
m) 1* 0*10
n) 00* 11*
o) (0+1)*11(1+0)*
2. Partiendo de la definicin de que un Autmata Finito Determinstico (AFD) est
dado por la quntupla: A= (Q, , f, q0, F) donde:
Q es un conjunto de estados.
es el alfabeto de entrada
f: Q X Q es la funcin (total) de transicin.
q0 Q es el estado inicial.
F Q es el conjunto de estados finales.
Y que para el ejercicio, el autmata se define como:
, A = ({q0, q
1, q
2, q
3} , {0,1} , f , q
0, { q
2})
Representado mediante el grafo:
-
7/28/2019 guia_col1_2013_I
10/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
EN UN SIMULADOR (YA SEA JFLAP O VAS)
Plsmelo en el simulador Realice la tabla de transicin correspondiente. Compruebe el lenguaje aceptado Identifique la expresin regular que permite identificar que cadenas
son vlidas y que acepta el autmata. Identifique que denotacin de estados est errada y corrjala.
3. Acorde al autmata del ejercicio N 2, Realice:
Identifique si es un AFD AFND y justifique por qu. Si dado el caso es un AFND convirtalo en el simulador a un AFD y
plsmelo en el trabajo sus cadenas vlidas. Analice si son lasmismas cadenas que acepta al autmata antes de convertirlo.
El nuevo AFND debe plasmarlo en el simulador.
Compruebe el lenguaje aceptado Identifique la expresin regular que permite identificar que cadenas
son vlidas y que acepta el autmata. Analice si la ER y el Lenguaje aceptado es el mismo o no al ejercicio
Nmero 2. Justifique sus respuestas.
4. Para el siguiente Autmata que acepta el lenguaje:
L = { {x,y,z}* =x*yz 2, i >= 0}
Realice las siguientes actividades:
Determine si es un AFD AFND Encuentre la ER Grfico en un diagrama de Moore Realice la tabla de transicin De cinco (05) ejemplos de cadenas vlidas que acepte el autmata Recrelo en el simulador
5. Construya un autmata que reconozca cadenas enmarcadas dentro de laexpresin regular: (1 + 0)* Tenga en cuenta que debe incluir cadenas vacas
del tipo Se recomienda primero realizarlo en papel (graficarlo a mano alzada antes dellevarlo al simulador.
-
7/28/2019 guia_col1_2013_I
11/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
Identifique los elementos de la tupla a que corresponda ese autmata ydescrbalos.
Realice el diagrama de Moore en el simulador y plsmelo en el trabajo. Construya Tabla de Transicin. En el simulador demuestre una cadena vlida haciendo el recorrido por
cada paso de estado. Identifique el lenguaje que reconoce.
6. Construya un Autmata que acepte el siguiente Lenguaje: L = 00*11*
Identifique sus componentes (la tupla que es) Constryalo en los simuladores. Demustrelo con al menos cinco cadenas vlidas. Demuestre tres cadenas
no vlidas y justifquelas por qu no son vlidas comparadas con laexpresin regular.
Identifique y justifique si su diseo de Autmata es AFD AFND Cree las tablas de transicin Plasme el diagrama de Moore
7. Para el siguiente autmata:
Identifique sus componentes (la tupla que es) Identifique si es un AFD o un AFND o si es un autmata de landa
transiciones. Justifique sus repuestas. Constryalo en el simulador Identifique claramente las cadenas y subcadenas vlidas y justifquelas. Plasme en el trabajo los grficos generados. Identifique la expresin regular y el lenguaje que representa Plasme la tabla de transicin.
-
7/28/2019 guia_col1_2013_I
12/12
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
Nombre escuela: Escuela de Ciencias Bsicas Tecnologa e Ingeniera
Nombre programa: Ingeniera de Sistemas
8. Construya un Autmata Finito Determinstico (AFD) de tres (3) estados queacepta dentro de su lenguaje la palabra unad
Identifique sus componentes (la tupla que es) Constryalo en los simuladores. Cree las tablas de transicin Plasme el diagrama de Moore Escriba la expresin regular que represente.
9. Para el siguiente autmata finito determinista dado por:
M = ({q0, q1, q2, q3} , {0, 1} , , q0, {q1})
Donde la funcin : {q0, q1, q2, q3 } {0, 1} {q0, q1, q2, q3} viene dada por:
(q0, 0) = q0 (q0, 1) = q1
(q1, 0) = q0 (q1, 1) = q2
(q2, 0) = q3 (q2, 1) = q1
(q3, 0) = q3 (q3, 1) = q2
Plsmelo en los simuladores. Realice el diagrama de Moore.
Identifique la tabla de transicin correspondiente. Verifique el lenguaje aceptado y las cadenas vlidas para el autmata. Identifique la expresin regular que lo representa.
10. Para el siguiente autmata:
Identifique sus componentes (la tupla que es) Recrelo en los simuladores
Realice la tabla de transicin.
Qu tipo de Autmata es (Justifquelo).
Identifique la ER y el Lenguaje que acepta Que cadena reconoce. (Demustrelo y grafquelo en el simulador).