RE:Maquina de turing
Publicado por
moy (1 intervención) el 05/06/2008 17:34:24
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <string.h>
typedef struct nodo {
char letra;
char est;
struct nodo *siguiente;
}estado;
estado *inicial, *final;
int bandera=0;
//***************************************>> INFO <<********************
void info(void){
clrscr();
printf("
Este programa simula el funcionamiento de una Maquina de Turing como
");
printf(" aceptor de una palabra bajo el lenguaje...
");
printf("
L={a* b}
");
printf("
DEFINICION: Lenguaje reconocido por la Maquina de Turing:
");
printf("
Esta compuesta por:
");
printf(" MT={Q,E,T,s,X,F,f}
");
printf(" Q Conjunto Finito de Estados {A,B}
");
printf(" E Alfabeto de Entrada {0,1}
");
printf(" T Alfabeto de la Cinta {0,1,X}
");
printf(" s Estado Inicial {A}
");
printf(" X Simbolo Blanco {@}
");
printf(" F Estado Final {B}
");
printf(" f Funciones de Transiciones {f}
");
printf(" Quedar¡a Definida para este programa de la siguiente forma:
");
printf(" MT=({A,B},{0,1},{0,1,X},A,@,{B})
");
printf(" Donde las funciones de Transiciones (f) ser n:
");
printf(" ÉÍÍÍÍÍËÍÍÍÍÍËÍÍÍÍÍ»
");
printf(" f º b º a º @ º
");
printf(" ÉÍÍÍÎÍÍÍÍÍÎÍÍÍÍÍÎÍÍÍÍ͹
");
printf(" º A º BbD º AaP º A@P º
");
printf(" ÌÍÍÍÎÍÍÍÍÍÎÍÍÍÍÍÎÍÍÍÍ͹
");
printf(" º B º AbP º AbP º A@P º
");
printf(" ÈÍÍÍÊÍÍÍÍÍÊÍÍÍÍÍÊÍÍÍÍͼ
");
printf(" P=Parar Movimiento
");
printf(" D=Movimiento del cabezal hacia la Derecha
");
printf("
GRUPO N§ "1"");
getch();
}
//***************************************>> PALABRA <<******************
void palabra(char letra, char est){
estado *nuevo;
nuevo=(estado*)malloc(sizeof(estado));
nuevo->letra=letra;
nuevo->est=est;
nuevo->siguiente=NULL;
if(inicial==NULL)
inicial=nuevo;
else final->siguiente=nuevo;
final=nuevo;
}
//***************************************>> BORRAR <<******************
void borrar(void){
nodo *temporal;
while(inicial!=NULL)
{
temporal=inicial;
inicial=inicial->siguiente;
free(temporal);
}
}
//***************************************>> VERIFICAR <<****************
int verificar(void){
estado *temporal;
int contadora,contadorb,contador;
temporal=inicial;
contadora=contadorb=contador=0;
while(temporal!=NULL){
if(temporal->letra=='a')contadora++;
if(temporal->letra=='b')contadorb++;
if(temporal->letra=='@')contador++;
temporal=temporal->siguiente;
}
if(contadorb==1 || contador==1) return 1;
else return 0;
}
//***************************************>> MOSTRARGRAFO <<***********
void mostrargrafo(){
estado *temporal, *anterior;
temporal=inicial;
if (temporal->letra=='a' || temporal->letra=='b') {
printf("
");
while(temporal->siguiente!=NULL) {
anterior=temporal;
printf(" (%c) -------------> (%c) con %c
",temporal->est,temporal->est,temporal->letra);
temporal=temporal->siguiente;
if(temporal->siguiente==NULL)
printf(" (%c) -------------> (%c) con %c
",anterior->est,anterior->siguiente->est,final->letra);
}
}
else{ printf("(A) -------------> (A) con @
");
printf("(A) -------------> (B) con b");
}
}
//***************************************>> INICIO <<*********************
void main(void)
{
char vector[30],opc;
int op,i;
do
{
clrscr();
printf(" * *
");
printf(" * ®1¯ Informaci¢n del Programa *
");
printf(" * *
");
printf(" * ®2¯ Ingresar Palabra a Analizar *
");
printf(" * *
");
printf(" * ®3¯ Iniciar Analisis de la Palabra *
");
printf(" * *
");
printf(" * ®4¯ Salir *
");
printf(" * *
");
printf(" ****************************************************
");
printf("
Elija una opci¢n: ");
scanf("%d",&op);
fflush (stdin);
switch (op)
{
case 1:
info(); break;
case 2:
if(bandera==0)
{
borrar();
printf("
Ingrese una palabra a ser analizada: ");
scanf("%s",vector);
fflush(stdin);
for(i=0;i<strlen(vector);i++)
{
if(vector[i]=='a') palabra(vector[i],'A');
if(vector[i]=='b'|| vector[i]=='@') palabra(vector[i],'B');
}
bandera=1;
printf("
®PALABRA CARGADA¯");
getch();
break;
}
else{
printf("
<< Ya Ingreso una Palabra >>");
printf("
¨Desea ingresar otra Palabra? (s/n): ");
opc=getch();
if (opc=='s') {bandera=0;break;}
}
case 3:
clrscr();
printf(" ****************************************************
");
printf(" ***** maquina de turing *****
");
printf(" ****************************************************
");
if(verificar()==1)
{
printf("
La Palabra Ingresada fue: %s
",vector);
mostrargrafo();
printf("
>>> PALABRA ACEPTADA <<<");
}
else{
printf("
La Palabra Ingresada fue: %s
",vector);
printf("
>>> PALABRA NO ACEPTADA <<<");
printf("
Recuerde que el Lenguaje de este Aut¢mata es L={a* b} en minusculas");
}
getch();
break;
case 4: printf("
Presione una Tecla para Salir"); borrar();getch(); op=4; break;
default:
printf("
®® Opci¢n Incorrecta - Elija una Opci¢n Valida ¯¯
>>> Intente de Nuevo <<<");
getch();break;
}
}while(op!=4);
}