• Author / Uploaded
• Octavio Mercado Gomez

• Categories
• Matemáticas
• Informática y tecnología de la información
• Ciencia
• Tecnología (general)
• Ciencia filosófica

Citation preview

APORTE INDIVIDUAL MOMENTO 1

YANETH MARCELA RODRÍGUEZ VINASCO CÓDIGO: 1088248071

PRESENTADO A: ANGELA MARÍA GONZÁLEZ

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍAS E INGENIERÍAS CEAD DOSQUEBRADAS, PEREIRA AUTOMATAS Y LENGUAJES FORMALES MARZO DE 2016

DESARROLLO DE LA ACTIVIDAD 1 Dados los siguientes ítems, Autómatas Finitos Deterministas, Autómatas Finitos no Deterministas, lenguajes y expresiones regulares (ER), encuentre según corresponda: AFN / AFD

LENGUAJE

L = {w|w tiene al menos una a y a tiene al menos una b} sobre {a, b}

2

3

4

L={w|w que inicie por b y b tiene al menos una a, sobre {a,b}} El lenguaje de las palabras que tiene abb o bba por subcadena

L={w|w inicia con una b acepta una o ninguna f y finaliza con a o

EXPRESIÓN REGULAR

b*(a(a*(b(a+b)*) ))

b(a*+ab*a)

a*b*(abb + bba)

(bf*a U dg*c)*

inicia con una d acepta una o ninguna g y finaliza con c, sobre {a,b,c,d,e,f,g }} L={w|w inicia con ab U c y finaliza con d, sobre {a,b,c,d}}

5

2

Para la expresión regular (cb)*ca(ab)*Ub(ba)*bU(ab)*a(ba)*b expresión regular y resuelva:

(ab U c)* d

simplifique la

(cb)*ca(ab)*+b(ba)*b+(ab)*a(ba)*b (cb)*ca(ab)*+ bb(ab)*+ (ab)*ab(ab)* [(cb)*ca+bb+(ab)*ab](ab)*

+¿ ¿ ( cb ) ca+bb+ ( ab ) (ab)¿ ¿ ¿

 



 

Describa la forma matemática del autómata Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo sino de justificarlo asociando la respuesta al diseño del autómata) Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales. Identifique el lenguaje que genera. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)



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). Genere tres cadenas válidas y dos no válidas.

 3

Si el autómata inicial (el de la ER4) es un AFD, genere un AFND que reconozca el mismo lenguaje; o por lo contrario si el autómata inicial es un AFND, genere un AFD que reconozca el mismo lenguaje.



Describa la forma matemática del autómata (bf*a U dg*c)*



Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). K={q0,q1,q2}

estados

∑={a,b,c,d,f,g} alfabeto S={q0}

estado inicial

F={q0}

estado final

Estados de transición

q0 q1 q2

a x q 0 x

b q 1 x

c x

x

q 0

δ ( q 0,b )=q 1

x

d q 2 x x

f x

g x

q 1 x

x q 2

δ ( q 0,d ) =q 2 δ ( q 1 , a ) =q 0 δ ( q 1 , f )=q 1 δ ( q 2 , c )=q 0 δ ( q 2 , g )=q 2 Verificando con VAS



Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

El autómata se posiciona en su estado inicial a la espera de una palabra para verificar la secuencia, para este caso se eligió la cadena bffa.

Cuando se ingresa la primera letra, la “b” se observa que el autómata cambia de estado y pasa al estado q1

Como los siguientes caracteres son ff el autómata permanece en este mismo estado tantas veces como sea ingresada, para nuestro caso dos iteraciones.

Por último al ingresar la “a” regresamos al estado inicial, el cual para este caso es también nuestro estado final o aceptador. Vemos que el recuadro azul donde se encuentra el alfabeto se torna color verde, lo que quiere decir que esta palabra fue aceptada por el autómata. 

Muestre el diagrama de Moore generado en JFLAP y en VAS

1Diagrama de Moore JFLAP

2 Diagrama de Moore en VAS





Identifique la ER asociada al nuevo diseño y compárela con la expresión regular simplificada (es decir analícelas con dos cadenas válidas y con dos no válidas). Para ello debe identificar en una tabla la jerarquía de operadores regulares, identificando con colores las sentencias matemáticas. Para ello apóyese en el video: http://youtu.be/JZPAHHA2PnE (minuto 14 al 33). O en el video. http://youtu.be/wGTxhnPXcw4