DESARROLLO

PARTE 1: Dada la siguiente tabla de transicin:

(Ntese que hay interacciones con smbolo vaco, diferente a cadena vaca)

1. Exprese el autmata en notacin matemtica. Identifique que tipo de autmata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo).

Autmata en notacin matemtica:

Tipo de autmata: Es una AFD porque la funcin de transicin indica a qu estado se va a pasar sabiendo cul es el estado actual y el smbolo que se est leyendo. No es simplemente una relacin lo que implica que para un estado y un smbolo del alfabeto dados, habr un y solo un estado siguiente.2. Identifique los elementos (tupla que es). Debe explicar y describir cada elemento y la funcin y significado en el autmata. Conceptos y definiciones adicionales.

= (K, S, 0, , ) = {0, 1, 2, 3} o S = {, , } 0 = {3} 3. Identifique el lenguaje que genera. L(M) = { x * , F,(s,x) * M (, )}.

La configuracin de un autmata finito (AF) es un elemento (q,) (K x *) est dada por:

Configuracin inicial: (q0, ) donde q0 es el estado inicial y la palabra de entrada. Configuracin de parada: cualquier configuracin en la que el autmata puede parar su ejecucin, bien porque se haya procesado toda la entrada o bien porque se haya llegado a una situacin donde no es aplicable ninguna transicin. Configuracin de aceptacin: (qF, ) donde qF, es un estado final del autmata. Una vez alcanzada esta configuracin el autmata puede aceptar la palabra.4. Muestre en el simulador (grficamente) como recorre una cadena vlida. Explique cada secuencia.Simulador de secuencia zyInicia en q0, pasa a q1 y finaliza en q3.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 ofrezcan uno u otro).- Diagrama Moore generado en JFLAP.

- Diagrama Moore generado en VAS.

Similitudes: en ambas podemos ver la autmata, sus conexiones y elementos, nos permiten conocer su estructura, ambas son grficas y fciles de manejar.

Diferencias: El VAS nos permite ver la notacin matemtica de la autmata, mientras JFLAP no lo deja ver.

JFLAP permite borrar los errores ms fciles con la x.

6. Identifique el lenguaje que representa: (tenga en cuenta como se plasma o identifica un lenguaje aceptado: mdulo pgina 47 leccin 10)

( + ) * ( + )( + ) * ={ {, , }*| =(, )* (, )}7. Genere tres cadenas vlidas y dos no vlidasCadenas validas:Para el automata

La cadena valida es: abbaababbab

cadenas no validas

aaa

abaBIBLIOGRAFACarlos Alberto Amaya Tarazona, (2014). Mdulo Acadmico de Autmatas y Lenguajes Formales. Extrado el 28 de Febrero del 2014 desde http://datateca.unad.edu.co/contenidos/301405/2014-I/MODULO2014-I/AUTOMATAS_Y_LENGUAJES_FORALES_2014-I.pdf