Automata

Solo disponible en BuenasTareas
  • Páginas : 2 (361 palabras )
  • Descarga(s) : 0
  • Publicado : 14 de febrero de 2012
Leer documento completo
Vista previa del texto
Proyecto 2

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....
tracking img