Actividad Colaborativa Momento 1 1Trabajo Grupal

SANDRA GALLO GÓMEZ Cod 52035770

YON IVAN MÁRQUEZ BUITRAGO.Cod. 82391374

TutorANGELA MARIA GONZALEZ

Marzo 2015.

Universidad Nacional Abierta y a Distancia UNAD Zona Centro Cead Arbeláez.

Ingeniería de Sistemas. Autómatas y Lenguajes Formales

Grupo 33

Introducción

Para el presente trabajo colaborativo, se debe presentar como producto 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).. Para esta realización podemos apoyarnos en alguno de los dos simuladores que nos presentan (JFLAP o VISUAL AUTOMATA SIMULATOR) Los gráficos y análisis de cada simulador son los que se exportaran al documento de Word. Debemos entregar los archivos generados por el simulador en una carpeta. Debemos apoyarnos en usar un editor de fórmulas para plasmarlas.

ii

Actividad IndividualProblemas a Desarrollar

1. Las expresiones regulares (ER), pueden también escribirse de otras formas o con otra secuencia de operadores o distribución de símbolos. En general es una forma matemática que representa el Lenguaje que genera un Autómata. Y esas expresiones regulares siempre serán válidas siempre y cuando representen exactamente el mismo lenguaje para un Autómata. Concluyendo, para un Autómata, puede haber más de una ER que representa el mismo lenguaje ya sea que esa ER sea minimizada, extensa, equivalente o como se prefiera escribir. Solo que en los diseños óptimos computacionales siempre se buscará la mejor ER (corta o mínima) para efectos de la mejor simulación o para llevarlas a lenguajes de programación en la creación de soluciones computacionales (solucionar problemas - Algoritmos) Dados los siguientes ítem, Autómatas Finitos Deterministas, Autómatas Finitos no Deterministas, lenguajes y expresiones regulares (ER), encuentre según corresponda:

AFN / AFD LENGUAJE EXPRESIÓN REGULAREJ1 L= {w | w

tiene al menos una a y tiene al menos una

b} sobre {a,b}

aa¿b (a+b )¿+bb¿a (a+b )¿

EJ2 L= {w | w tiene las

palabras que empiezan por b y terminan en a} sobre

{a,b}

bb¿aa¿+bb¿a (bb¿a )¿

¿bb¿a (a+bb¿a )¿

EJ3 El lenguaje de las palabras

que tiene a abb o bba por subcadena

(a a¿b+baa¿b ) (aa¿b )¿b (a+b )¿+bbb¿a (a+b )¿

1

EJ4 El lenguaje de las palabras que tiene

a d seguida con varias o ninguna g y terminan con c o

b seguida con varias o ninguna f y terminan con a; por subcadena.

Sobre {a,b,c,d,f,g}

b f ¿a+d g¿c

EJ5 El lenguaje de todas las

palabras que contienen una o varias ab o c y terminan en

d.Para {a,b,c,d}

(ab∪c )¿ d(ab+c )¿d

2. PARA LA EXPRESION REGULAR:

(cb )¿ca (ab )¿∪b (ba )¿b∪ (ab )¿a (ba )¿bSIMPLIFIQUE LA EXPRESIÓN REGULAR YRESUELVA:

1) Describa la forma matemática del autómata,

(cb )¿ca (ab )¿+b (ba )¿ b+(ab )¿a (ba )¿bc¿b¿caa¿b¿+bb¿a¿b+a¿b¿ab¿a¿bc¿b¿caa¿+bb¿a¿b+a¿b¿aba¿b¿(c¿¿¿ca+bb+ab)¿

La forma matemática del autómata se expresa de la siguiente forma: M = [(q0,q1, q2, q3, q4),(a,b,c), δ ,q0,( q4)]

M= {an0, bm0, (cñ0,c,a), (b,b),(a,b)} │ n, m, ñ ≥ 0}

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

2

R/ Este es un autómata AFND ya que se determinan varias rutas para llegar al estado final, en este caso se tienen 3 rutas, una por medio de q1, otra por q2 y otra por q3, seria determinista si solo tuviese una ruta.

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

R/ M es un quíntuplo (K, Σ, δ, s, F), donde:K = {q0, q1, q2, q3, q4}, identifica el conjunto de estados del autómata

Σ = {a, b, c, λ}, es el alfabeto de entrada“s” es el estado inicial, en nuestro caso {q0}“F” es un conjunto de estados finales, en nuestro caso {q4} : K x ∑ → K es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.

Donde la función : {q0, q1, q2, q3, q4} x {a, b, c, λ}-> {q0, q1, q2, q3, q4} viene dada por:

3

Conceptos y definiciones adicionales. 4) Identifique el lenguaje que genera.

R/ . L= {w | w palabras que pueden iniciar por a, b o c; pero las palabras que inician en a o b, solo pueden terminar en b; y las palabras que inicien en c solo pueden terminar en a y b} sobre {a, b, c}

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

R/ .La secuencia la mostramos en VAS, vamos a ejecutar la cadena “cbca”

Paso 1: Inicializa la ejecución del autómata desde el estado q0

4

Salta de q0 a q1 haciendo transición con la letra c

Salta de q1 a q3 haciendo transición con la letra b

5

Salta haciendo un retorno de q3 a q1 haciendo transición con la letra c

Finaliza el autómata haciendo transición de q1 a q4 con la letra a

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

R/ . Diagrama de Moore en JFLAP y en VAS

JFLAP VAS

6

SIMILITUDESEl manejo es muy intuitivo

Ambos se trabajan con el java, si este no esta en el equipo no funcionanGeneran archivos de facil manejo y la simulacion d e los automatas es muy sencilla

DIFERENCIASGuarda bien los datos No guarda los estados ni las transiciones, solo

conserva el graficoDificulta sacar la lista de transiciones ya que genera otras letras a los estados de los que uno originalmente le pone

Puedo sacar el listado de transiciones de una forma clara

Me parece mucho mas completo para elaborar los automatas, ya que tiene muchas opciones

en su menu

Es bastante limitado ya que no se pueden generar muchas d elas funciones que tiene el otro programa.

7

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

R/ .

8

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.

1. Describa la forma matemática del autómata2. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). 3. 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)4. Muestre el diagrama de Moore generado en JFLAP y en VAS5. 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

9

Conclusiones.

Aunque con dificultades, hemos entrado ene l mundo de los Autómatas, iniciando un recorrido muy interesante en este curso, es lastimoso que no todos los compañeros participen, ya que como se evidencia solo estamos trabajando dos de los cinco integrantes.

La comprensión de la temática aquí desarrollada nos da herramientas para que lleguemos a ser unos buenos profesionales, ya que esta temática es muy importante en el campo de la programación, además esta lógica aquí aprendida nos ayuda a entender como funcionan muchos de los sistemas actuales.

La existencia de los lenguajes regulares y su vinculación con otros artefactos lingüísticos-matemáticos, estudiados e incluso llevados a la práctica ha sido de vital importancia en el desarrollo de los mecanismos de procesamiento de lenguajes de computación

10

Lista de referencias

Alfonseca, M., J. Sancho, M. A. Orga, Teoría de Lenguajes, Gramáticas y Autómatas, Promosoft, 1997.

Cueva L., Juan Manuel, Lenguajes Gramáticas y Autómatas, Segunda Edición, 2001, Universidad de Oviedo.

Díaz Víctor, Cañete José Miguel, Lenguajes Formales y autómatas, Universidad de Sevilla, 2006

Hernández Rodríguez , Leonardo Alonso. Practique la Teoría de Autómatas Y Lenguajes Formales

Hopcroft, J.E., R. Motwani, J. D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación (2ª Edición), Prentice-Hall, 2000. Recuperado de https://books.google.com.co/books?id=3_xiZG8exjAC&pg=PA74&lpg=PA74&dq=El+lenguaje+de+las+palabras+que+tiene+a+abb+o+bba+por+subcadena&source=bl&ots=GZJgBuJF9Z&sig=kmKd8eZPbLnSD0t035Yc6_eEh4M&hl=es-419&sa=X&ved=0ahUKEwjY_9GGn5vLAhWJth4KHaycBr8Q6AEIGzAA#v=onepage&q=El%20lenguaje%20de%20las%20palabras%20que%20tiene%20a%20abb%20o%20bba%20por%20subcadena&f=false

Normas APA actualizadas. Recuperado de http://normasapa.com/plantilla-en-word-con-normas-apa-2015/

11