Automata
Problema:
1. Generar un AFD con su respectiva matriz de estados a partir de un grafo cualquiera, con el fin de compararlos con otros grafos y determinar si son o no isomorfos.2. Implementar un programa que analice y compare el grafo principal con los nuevos ingresados, por medio del mismo autómata .
Solución
1. Se debe realizar un grafo con el cual se generará surespectivo AFD el cual será implementado en un programa desarrollado en lenguaje C o Java donde al ingresar un nuevo grafo representado por una cadena determinada, debe compararla con el grafo principaly denotar con 1 para decir que son isomorfos o 0 si no son isomorfos.
Por ejemplo estos dos grafos son isomorfos
Imagen 1imagen 2
2. Las cadenas deben estar representadas de la siguiente forma
Por ejemplo para la imagen 2 la cadena seria:12-(1,2)-(1,4)-(1,5)-(2,3)-(2,6)-(3,4)-(3,7)-(4,8)-(5,6)-(5,8)-(6,7)-(7,8) Dónde:
Cada grupo simboliza las relaciones encontradas en el grafo
El primer número simboliza la cantidad de aristas
Se debe tener en cuentalo siguiente:
* Cada relación debe estar entre paréntesis y unidas por guiones (-)
* Los extremos de las relaciones se deben separar por comas(,)
* Después del número de aristas debe irun guion (-)
* Las relaciones deben estar ordenadas en forma ascendente y sin repetirse como se muestra en el ejemplo
3. El alfabeto que se utilizara será el siguiente y es el mismo para todos:= {1,2,3,4,5,6,7,8,9,0, , , ’,-}
Se debe presentar el programa y un documento anexo con el proceso realizado sobre los lenguajes (autómatas, matrices etc.)
Evaluación
1. Sustentación 5Puntos
2. Funcionamientos del programa 5 puntos
Requisitos
1. El programa debe funcionar correctamente para ser evaluado.
2. Desarrollar el documento en Word, letra Arial tamaño 11....
Regístrate para leer el documento completo.