Automatas Y Lenguajes Formales
Enviado por • 21 de Octubre de 2013 • 4.085 Palabras (17 Páginas) • 456 Visitas
1. Corrija la tabla de transición indicando el estado inicial y final.
2. Construya el diagrama de Moore correspondiente.
3. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta.
4. Identifique los elementos (tupla que es). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.
5. Identifique la ER que lo representa. Explique los operadores y cómo actúan en la función.
6. Identifique el lenguaje que genera.
7. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia.
8. 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 ofrezca uno u otro).
9. Genere la tabla de transición en VAS y plásmela en el documento, compárela con la plasmada en el ejercicio
10. Por último, identifique las cadenas válidas que generan las siguientes ER: muestre algunas, pero más que las cadenas identifique el lenguaje que representa. Seleccione una ER (solo una) y expórtela o genere el autómata o el diagrama de Moore que sea válido.
Los temas sobre autómatas, computabilidad, e incluso la complejidad algorítmica fueron incluidos de forma referencial y básica en cada unidad, ya que como la historia lo dice y de manifiesto propio, las ciencias de la computación han usado gran cantidad de ideas de muy diferentes campos para su desarrollo, y que la investigación sobre aspectos básicos podía cooperar y aumentar los avances de la computación.
Como elemento determinante para que el lector de manera progresiva y jerárquica comprende la lógica de este tipo de análisis matemático, están los conceptos previos y claros que se deben reconocer en el área de la matemática y la teoría de conjuntos, funciones, relaciones y principios fundamentales de la lógica, ya que estos temas no son tratados como temáticas en el libro, pero que tienen gran importancia en los fines para los que se creé este documento
Los temas sobre autómatas, computabilidad, e incluso la complejidad algorítmica fueron incluidos de forma referencial y básica en cada unidad, ya que como la historia lo dice y de manifiesto propio, las ciencias de la computación han usado gran cantidad de ideas de muy diferentes campos para su desarrollo, y que la investigación sobre aspectos básicos podía cooperar y aumentar los avances de la computación.
Como elemento determinante para que el lector de manera progresiva y jerárquica comprende la lógica de este tipo de análisis matemático, están los conceptos previos y claros que se deben reconocer en el área de la matemática y la teoría de conjuntos, funciones, relaciones y principios fundamentales de la lógica, ya que estos temas no son tratados como temáticas en el libro, pero que tienen gran importancia en los fines para los que se creé este documento
Conjunto Vacío: Es llamado también nulo y es aquel que no tiene elementos. Se denota
como . El conjunto vacío es un subconjunto de todos los conjuntos; por lo cual es válido
denotar: A para todo conjunto A.
Tamaño de un conjunto: El tamaño de un conjunto es el número de elementos que
contiene, y se representa como: |A| para un conjunto A.
Ejemplo 2 El tamaño de {1,2,3,4,5} es 5
E tamaño de {{a,b,c} , {a}} es 2 siendo el primero {a,b,c} y el segundo {a}
El orden de los elementos de un conjunto es irrelevante.
Ejemplo 3 El conjunto A = {{a,b}, {c}} y el conjunto B={{c},{b,a}} son iguales: A=B
Descripción matemática del contenido de un conjunto: Un conjunto se puede
especificar enumerando sus elementos entre llaves y separados por comas y esto es lo
que se llama definición por extensión. muchas veces y para el caso de la Teoría de
Autómatas que trata este libro, no es posible especificar elementos de un conjunto o
alfabeto porque el conjunto es infinito y entonces se usa una definición por comprensión, es
decir, haciendo referencia a otros conjuntos (conjuntos referenciales) y a propiedades que
los elementos puedan tener.
A través de desarrollo de la temática, y específicamente para poder describir autómatas,
lenguajes y leer expresiones regulares, tendremos que aprender a leer funciones de
transición, tuplas entre otros. Un buen ejercicio es empezar a interpretar lecturas y que
de forma general se definen como
Conjunto Vacío: Es llamado también nulo y es aquel que no tiene elementos. Se denota
como . El conjunto vacío es un subconjunto de todos los conjuntos; por lo cual es válido
denotar: A para todo conjunto A.
Tamaño de un conjunto: El tamaño de un conjunto es el número de elementos que
contiene, y se representa como: |A| para un conjunto A.
Ejemplo 2 El tamaño de {1,2,3,4,5} es 5
E tamaño de {{a,b,c} , {a}} es 2 siendo el primero {a,b,c} y el segundo {a}
El orden de los elementos de un conjunto es irrelevante.
Ejemplo 3 El conjunto A = {{a,b}, {c}} y el conjunto B={{c},{b,a}} son iguales: A=B
Descripción matemática del contenido de un conjunto: Un conjunto se puede
especificar enumerando sus elementos entre llaves y separados por comas y esto es lo
que se llama definición por extensión. muchas veces y para el caso de la Teoría de
Autómatas que trata este libro, no es posible especificar elementos de un conjunto o
alfabeto porque el conjunto es infinito y entonces se usa una definición por comprensión, es
decir, haciendo referencia a otros conjuntos (conjuntos referenciales) y a propiedades que
los elementos puedan tener.
A través de desarrollo de la temática, y específicamente para poder describir autómatas,
lenguajes y leer expresiones regulares, tendremos que aprender a leer funciones de
transición, tuplas entre otros. Un buen ejercicio es empezar a interpretar lecturas y que
de forma general se definen como
Conjunto Vacío: Es llamado también nulo y es aquel que no tiene elementos. Se denota
como . El conjunto vacío es un subconjunto de todos los conjuntos; por lo cual es válido
denotar: A para todo conjunto A.
Tamaño de un conjunto: El tamaño de un conjunto es el número de elementos que
contiene, y se representa como: |A| para un conjunto A.
Ejemplo 2 El tamaño de {1,2,3,4,5} es 5
E tamaño de {{a,b,c} , {a}} es 2 siendo el primero {a,b,c} y el segundo {a}
El orden de los elementos de un conjunto es irrelevante.
Ejemplo 3 El conjunto
...