AFD

[caballero-maldito]

hola saben casi nunca pido ayuda, solo que esta vez me veo en la necesidad je je veran llevo la materia de matematicas discretas nos han dejado un proyecto que consiste en programar un automata finito determinista (sin transiciones  epsilon(como se escriba))
no pido que me lo hagan pues ya comenze a programarlo de hecho ya tengo todo solo en una funcion que llamo analizar_transiciones(etc); la verdad no logro acomodar mis ideas, el problema que tengo en si es que los estados cambien de acuerdo a la cadena ingresada por el usuario, el programa debe pedir toda la quintupla es decir:

conjunto de estados
estado inicial
estado(s) final(es)
lenguaje del automata
y la tabla de transiciones, por ejemplo estado q0 con respecto a una "a" pasa al estado q1

les pongo mi codigo a continuacion si gustan primero corranlo para que vean lo que hace, donde tengo problemas o mas bien no se que diablos hacer para "seguir" la cadena ingresada por el usuario, si mi codigo esta algo confuso diganme y os explicare que es, lo estaba intentando hacer con arreglos de estructuras cada estructura es un estado pero creo que ese no es el camino je je saludos y disculpen las molestias, espero no me insulten ja ja ja o me traten de lammer, creo que con mi codigo demuestro algun conocimiento 

PD: esta hecho en C, utilizo el compilador en modo DOS, TC, BC como lo conozcan jeje, bajo win xp(valga la redundancia XD)


si esta muy abstracto espero compartan sus ideas o el "así lo haria yo" digo para que no gasten valioso tiempo tratando de parchar mi program je je

Código [Seleccionar] Expandir



//importante: los estados se almacenan como enteros es decir el estado q0 en realidad solo es 0, no se guardan como cadena "q0"
//le pongo la "q" cuando muestro los estados para que se vea mejor o se entienda, bueno ya me revolvi


#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <dos.h>

struct estado
{
int numero, destino[10];
char lenguaje[10];
};
typedef struct estado Estado;

void pedir_estados(int *estados,int *inicial,int final[10],int *aux);
void pedir_lenguaje(char lenguaje[10]);
int mostrar(char cadena[10]);
void transicion(int *estados,int *tam,char lenguaje[10],int transiciones[10][10]);
void mostrar_transiciones(int *estados,int *tam,char lenguaje[10],int transiciones[10][10]);
void asignar_estructura(int *estados,char lenguaje[10],int *tam,int transiciones[10][10],Estado Estructura[10]);
int analizar_transiciones(int *inicial,int *tam,int *tam2,int *aux,int *final,Estado Estructura[10],char cadena[10]);
void pedir_cadena(char cadena[10],int *tam2);

void main()
{
Estado Estructura[10];
char lenguaje[10];
char cadena[10];
int final[10];
int inicial;
int estados;
int transiciones[10][10]; //guarda los estados "destino" en la tabla de transiciones
int cont;
int tam; //tama¤o del lenguaje
int tam2;
int aux;   //total de estados finales
int aceptar;  //bandera que nos auxila a saber si la cadena fue aceptada o no
pedir_estados(&estados,&inicial,final,&aux);
pedir_lenguaje(lenguaje);
tam=mostrar(lenguaje);
transicion(&estados,&tam,lenguaje,transiciones);
mostrar_transiciones(&estados,&tam,lenguaje,transiciones);
asignar_estructura(&estados,lenguaje,&tam,transiciones,Estructura);
mostrar_transiciones(&estados,&tam,lenguaje,transiciones);


//este ciclo no es importante solo recuerda al usuario cuales son los estados finales
printf("\n\n\tEstados finales: ");
for(cont=0;cont<aux;cont++)
{
printf(" q%d ",final[cont]);
}
////////////////////////////////////////////////////////////////////////////////////

pedir_cadena(cadena,&tam);
aceptar=analizar_transiciones(&inicial,&tam,&tam2,&aux,final,Estructura,cadena);


if(aceptar>0)
{
printf("\n\n\tLa cadena es aceptada");
}
else
{
printf("\n\n\tLa cadena no es aceptada");
}
getch();
}

void pedir_estados(int *estados,int *inicial,int final[10],int *aux)
{

//int final[10];
//int inicial;
int cont;
//int aux;//numero de estados finales
//int estados;
clrscr();
printf("\n\tInserta el numero de estados: ");
fflush(stdin);
scanf("%d",&*estados);
printf("\n\n");
for(cont=0;cont<*estados;cont++)
{
delay(400);
printf("\n\n\tq%d",cont);
}
printf("\n\n\tEstado inicial: q");
fflush(stdin);
scanf("%d",&*inicial);
printf("\n\n\tCuantos estados finales tiene el automata?: ");
fflush(stdin);
scanf("%d",&*aux);
for(cont=0;cont<*aux;cont++)
{
printf("\n\n\tingresa el estado final %d: q",cont+1);
fflush(stdin);
scanf("%d",&final[cont]);
}
}
void pedir_lenguaje(char lenguaje[10])
{
printf("\n\n\tIngresa el lenguaje del automata,junto, ejemplo: abc\n\t: ");
fflush(stdin);
gets(lenguaje);
}
int mostrar(char cadena[10])
{
int cont;
int tam;
tam=strlen(cadena);
printf("\n\n\t");
for(cont=0;cont<tam;cont++)
{
printf(" -%c- ",cadena[cont]);
}
return tam;
}
void transicion(int *estados,int *tam,char lenguaje[10],int transiciones[10][10])
{
int cont;
int cont2;
printf("\n\n\tIngrese la tabla de transiciones\n");
for(cont=0;cont<*estados;cont++)
{
for(cont2=0;cont2<*tam;cont2++)
{
printf("\n\tq%d con respecto a una -> %c: q",cont,lenguaje[cont2]);
scanf("%d",&transiciones[cont][cont2]);
}
}
printf("\n\n\tCarga de transiciones completada con exito");
}
void mostrar_transiciones(int *estados,int *tam,char lenguaje[10],int transiciones[10][10])
{
int cont;
int cont2;
printf("\n\n\tTabla de transiciones\n");
for(cont=0;cont<*estados;cont++)
{
for(cont2=0;cont2<*tam;cont2++)
{
printf("\n\n\tq%d con respecto a una -> %c: q%d",cont,lenguaje[cont2],transiciones[cont][cont2]);
}
}
printf("\n\n\tCarga de transiciones completada con exito");
}
void asignar_estructura(int *estados,char lenguaje[10],int *tam,int transiciones[10][10],Estado Estructura[10])
{
int cont,cont2;
for(cont=0;cont<*estados;cont++)
{
Estructura[cont].numero=cont;   //asigna el numero del estado
for(cont2=0;cont2<*tam;cont2++)
{
Estructura[cont].lenguaje[cont2]=lenguaje[cont2];    //asigna el lenguaje
Estructura[cont].destino[cont2]=transiciones[cont][cont2];   //asigna el estado al que llevara el lenguaje
}
}
}
//pendiente, implementacion de escructura "Estado"
int analizar_transiciones(int *inicial,int *tam,int *tam2,int *aux,int *final,Estado Estructura[10],char cadena[10])
{
int cont,cont2;
int estado_activo;
int bandera=0;
estado_activo=*inicial;
for(cont=0;cont<*tam2;cont++)
{

for(cont2=0;cont2<*tam;cont2++)
{
if(cadena[cont]==Estructura[cont].lenguaje[cont2])
{
estado_activo=Estructura[cont].destino[cont2];
}
/*else
{
cont2++;
}*/
}
}
for(cont=0;cont<*aux;cont++)
{
if(estado_activo==final[cont])
{
bandera++;
}
}
return bandera;
}
void pedir_cadena(char cadena[10],int *tam2)
{
printf("\n\n\tIngresa la cadena a evaluar, maximo 10 caracteres: ");
fflush(stdin);
gets(cadena);
*tam2=strlen(cadena);
}




EI: juntando mensajes.

¬¬ gracias
ja ja aja ja ja jaaj ja ja ja

ya termine el program estoy por la version 3.5 hoy pienso hacer la 4
el codigo que meti al principio corresponde a la version 1 ja ja ja ja estructuras que risa me dan, resolvi mi problema con arreglos bidimensionales tal vez lo ideal en este problem, saludos, creo k nadie ha entrado aparte de yo XD

[Ragnarok]

Este ejemplo es de los que quedan mejor con programación orientada a objetos (POO), pero igualmente lo puedes hacer con un tipo abstracto de datos (TAD), o... como lo has hecho, que es una chapuza pero funciona.

El caso es que tienes un tipo de datos, que es un autómata, que a su vez tiene varios tipos o campos, los estados, la tabla de transiciones, etc.

A este autómata le pasas una cadena y ves si la acepta, en tu caso, sin POO sería una función para manejar este TAD, le pasas una variable del TAD, la cadena y te devuelve un booleano (el tipo de datos en C tendrá que ser un int, char o lo que quieras, pero semánticamente funciona como booleano).

Para ver si acepta la cadena lo que tienes que hacer (si no tienes iniciado el autómata por defecto) es iniciar el autómata en el estado inicial (son dos campos, estado actual y estado inicial) se hace con la función iniciar aplicada a ése tipo de datos, que te devuelve el mismo autómata en el estado inicial.

Luego le vas pasando caracter por caracter, lo mismo, otra función, le pasas un caracter y el autómata, internamente mira la tabla de transiciones y el estado actual, y lo actualiza con la transicioń correspondiente.

Y cuando se acaba la cadena lo que haces es mirar si el estado actual está en la lista de estados finales, también otra función de manejo del TAD. Y el retorno de esa función es el retorno de la función para comprobar si acepta una cadena.

Se hace un poco duro porque manejar TADs es más pesado que manejar objetos, al estar programando, pero tampoco tiene mucho.

Más o menos es como lo has hecho, pero con un TAD es programación estructurada y como lo tienes es un caos tienes que entender que en programación es más habitual hacer middleware, librerías, etc. que programas completos, y el código que has hecho es poco reutilizable. Imagina el lío que tendría que montar alguien si quisiera por ejemplo hacer una interfaz gráfica para manejar autómatas.

[Ragnarok]

Se tiene que poder hacer con muchas menos líneas que 1800, pero muchas menos.

Para analizar las transiciones tienes que tener una doble tabla, por estado y por carácter que entra, teniendo por valor el estado al que llega, puedes hacer lo mismo con una matriz. Es complejidad de orden constante, no fuerza bruta...

[peatalex199]

buen programa!!!podrias poner tu version mas reciente del programa te lo agradeceria