Upload
amvillaloboss
View
217
Download
0
Embed Size (px)
DESCRIPTION
momento 1
Citation preview
Automatas y Lenguajes Formales
Momento 1
Dairo Cardona Morales - Código 94.286.083
Viviana Helena Celis Navarro - Código 63536497
Orlando Trujillo – Código 12139308
José Libardo Ramos Ricardo - Código 1.081.405.245
Grupo 77
Tutor
Carlos Alberto Amaya Tarazona
Universidad Nacional Abierta y a Distancia
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Marzo 04 de 2015
Dado el siguiente Autómata M finito: donde:
{ } { } Es el estado inicial
Donde la función de transición está dada por:
{ } { } { } { }
1. 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)
Tabla de Transición
Es un Autómata Finito No Determinístico (AFND), porque cuando se
encuentra en el estado , se le permite cambiar de estado aún sin tener
que leer algún símbolo de entrada, o sea que el primer símbolo de entrada
puede ser vacío.
2. Identifique los elementos (tupla que es) (Asociados 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.
La tupla (secuencia ordenada en una lista con un número limitado de objetos) del ejercicio propuesto es:
Representa el alfabeto de entrada, en el ejercicio propuesto se compone de los elementos {a, b, c}
Representa el estado o estados finales del autómata, en el ejercicio
propuesto son { }
Representa el conjunto de estados que tiene el autómata, en este
caso son los siguientes: { }
Representa el estado inicial del autómata, en este caso es { }
Representa la función de transición del autómata, en este caso es:
{
}
3. Identifique el lenguaje que genera.
El lenguaje que genera el autómata propuesto es el siguiente:
{
}
4. 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)
Imagen 1: El autómata inicia en el estado
Imagen 2: El autómata recibe como válido el primer símbolo de la cadena, correspondiente
al caracter “a” y pasa al estado
Imagen 3: El autómata recibe como válido el segundo símbolo de la cadena,
correspondiente al caracter “b” y pasa al estado el cual por ser un estado final, se
muestra en el simulador como cadena válida, pero la en realidad aún no ha terminado de
leer la cadena introducida.
Imagen 4: El autómata recibe como válido el tercer símbolo de la cadena, correspondiente
al caracter “c” y pasa al estado
Imagen 5: El autómata recibe como válido el cuarto símbolo de la cadena, correspondiente
al caracter “a” y pasa al estado final , donde finaliza el recorrido del autómata y se
evidencia en color verde como una cadena válida.
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 ofrezcan uno u otro).
Diagrama de Moore generado en JFLAP
Diagrama de Moore generado en VAS
DIFERENCIAS
Concepto JFLAP VAS
Identificación de Estados Toma el nombre
automáticamente al agregar el estado
Se debe especificar manualmente antes de
agregar el estado
Herramientas Se puede convertir a
gramática No se puede convertir a
gramática
Herramientas No permite generar tabla
de transiciones Permite generar la tabla
de transiciones
SIMILITUDES
Concepto JFLAP VAS
Recorrido del autómata
Permite ver paso a paso el recorrido que hace el autómata por la cadena
introducida
Permite ver paso a paso el recorrido que hace el autómata por la cadena
introducida
Opción de guardar Permite guardar el
autómata en diferentes formatos de imagen
Permite guardar el autómata en diferentes
formatos de imagen
Portabilidad
La aplicación es autoejecutable y no
requiere ser instalada en el equipo
La aplicación es autoejecutable y no
requiere ser instalada en el equipo
6. Encuentre la expresión regular(ER)de forma que la asocie y la halle con el procedimiento de convertir un AF a ER, Debe quedar plasmado el procedimiento indicando y asociando los componentes de la ER al autómatas (diagrama de moore)
a. Se toma el autómata inicial
b. Se añade un nuevo estado inicial y un nuevo estado final. Lo que quiere
decir que deja ser inicial y dejan de ser finales
c. Se elimina el nodo teniendo en cuenta las trayectorias que pasan por
él.
d. Se elimina el nodo teniendo en cuenta las trayectorias que pasan por
dicho nodo.
e. Se elimina el nodo teniendo en cuenta las trayectorias que pasan por
dicho nodo.
f. Se elimina el nodo teniendo en cuenta las trayectorias que pasan por
dicho nodo.
g. Se elimina el nodo teniendo en cuenta las trayectorias que pasan por
dicho nodo.
h. Se realiza fusión de expresiones paralelas.
La Expresión Regular (ER) obtenida corresponde a:
7. Genere tres cadenas válidas y dos no válidas
Cadenas Válidas:
Cadenas No Válidas:
Las cadenas anteriores fueron verificadas en JFLAP, donde se obtuvo la confirmación de lo solicitado.
8. Plasme las tres cadenas válidas para cada ER en una tabla (identificando jerarquía de operadores regulares, identificando colores). Para ello apóyese en el video: http://youtu.be/JZPAHHA2PnE (minuto 14 al 33). O en el video http://youtu.be/wGTxhnPXcw4
Cadenas Válidas:
9. Identifique en la misma tabla por que las dos cadenas seleccionadas no se
aceptan o en qué parte se trunca la jerarquía y orden de los operadores.
Se analiza la primera cadena no válida:
En el análisis se observa lo siguiente:
En la primera ocasión no se puede ejecutar la cadena porque el segundo caracter
debe ser una
En la segunda ocasión no se puede ejecutar la cadena porque el segundo caracter
debe ser una , además también requiere la presencia del caracter
En la tercera y cuarta ocasión no se puede ejecutar la cadena porque el segundo
caracter debe ser una o en caso contrario solo se puede leer una sola
Se analiza la segunda cadena no válida:
En el análisis se observa lo siguiente:
En la primera ocasión no se puede ejecutar la cadena porque no existe la
posibilidad de leer el último caracter
En la segunda ocasión no se puede ejecutar la cadena porque no existe la
posibilidad de leer el último caracter , además se requiere de la presencia al final
por lo menos de los caracteres
En la tercera ocasión no se puede ejecutar la cadena porque no existe la
posibilidad de leer el último caracter , adicional a ello en la última posición
debería ir el caracter
10. Proponga un diseño de un autómata (solo en diagrama de moore) que
reconozca el mismo lenguaje que el autómata de este ejercicio y que tenga como características que sea un AFD y tenga un solo estado final.