AUTOMATAS Y LENGUAJES FORMALESMOMENTO 1

DANIEL EDUARDO RAMREZ MARTNEZ

CODIGO: 1075236034

GRUPO: 14

TUTOR: CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ECBTI

CCAV NEIVA

2014

Problemas a desarrollar:

Dada la siguiente tabla de transicin:

1. Exprese el autmata en notacin matemtica (Tome como referencia, ejemplo 24 pgina 43 del mdulo). Identifique que tipo de autmata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo).

Tenemos: A = (K,, q0,,F) K = {q0, q1, q2, q3,q4} = {0,1} q0 Es el estado Inicial F = q2,q4 donde la funcin de transicin est dada por: : {q0, q1, q2, q3,q4 } {0, 1} {q0, q1, q2, q3,q4} q0 { q2,q4}Este autmata es un AFD, porque llega a un determinado punto y no puede tener ms estados.2. Identifique los elementos (tupla que es) (Asociadas con los elementos del autmata del ejercicio propuesto). Debe explicar y describir cada elemento y la funcin y significado en el autmata. Conceptos y definiciones adicionales.

A2= ( = {0,1}, K= {q0, q1, q2, q3, q4}, , q0, F= {q2, q4})Encontramos el Autmata A2, cuyo alfabeto est conformado por los smbolos 0, 1 y tiene un conjunto de estados Q conformado por los estados q0, q1, q2, q3, q4, que tiene un estado inicial q0y dos estados finales F= q2, q4, y con una funcin de transicin .A continuacin encontramos las siguientes definiciones.Autmata: La palabra autmata evoca algo que pretende imitar las funciones propias de los seres vivos, especialmente relacionadas con el movimiento, por ejemplo el tpico robot antropomorfo. Un ejemplo de una maquina real que automatiza un proceso puede ser una mquina empacadora de algn producto que se fabrique en serie y con una serie de instrucciones, pasos y caractersticas definidas e iguales para cada salida (producto final).

Alfabeto:Un alfabeto es un conjunto finito A. Sus elementos se llamaran smbolos o letras. Para denotar el alfabeto se usara el smbolo o en algunos casos se especificaran con las primeras letras maysculas del abecedario, dependiendo como se formule el problema. Los smbolos de un alfabeto pueden ser nmeros, letras, entre otros y suelen estar escritos en minsculas.

Estado: Un estado es un conjunto particular de instrucciones las cuales sern ejecutadas en respuesta a la entrada de la mquina. Se puede pensar en el estado como algo anlogo a la memoria principal de la computadora.

Funcin de transicin: Una funcin de transicin en teora de autmatas,es una funcin que define las transiciones entre losestados de unaMquina de Turing,de un autmata finito o de otro tipo de autmatas. Se describe mediante una tabla de

HYPERLINK "http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados" \t "_blank" transicin de estados.3. Identifique el lenguaje que genera.

L = {{0,1}* = 010, i 0 }Reconoce el lenguaje de todas las cadenas posible dentro de todo el conjunto de combinaciones posibles {0,1}* de tal manera que esas cadenas empiecen por un 0, seguidas de ninguna, una o ms 12 y que finalizan con un 0.

4. Muestre en el simulador (grficamente) como recorre una cadena vlida. Explique cada secuencia. (No se trata solo de captura las imgenes, estas deben ser explicadas en pi de pgina o de lo contrario no tienen validez).

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

6. Identifique la ER del autmata y Plasme tres cadenas vlidas y tres no vlidas en una tabla (identificando jerarqua de operadores regulares, identificando colores). Para ello apyese en el video: http://youtu.be/JZPAHHA2PnE (minuto 14 al 33). O en el video http://youtu.be/wGTxhnPXcw4

7. Justifique o explique segn la jerarqua y funcin de los operadores de ER en qu parte se trunca la jerarqua y orden de los operadores para las cadenas no vlidas de la tabla anterior .

8. De la tabla de transicin dada y del autmata asociado a esa tabla, genere la ER (no desde el simulador JFLAP), genrela de forma manual y explique cada sentencia asociada al autmata o diagrama de moore.