Este es el codigo de un programa que puede generar un automata finitio determinista a partir de su tabla, las tablas empledas estan generadas por los siguientes automatas.
Bueno por si acaso, la matriz de booleanos es la que determina cual de los estados es estado de aceptación (true) y cual es estado de error(false). (Y)
EL CODIGO DE LA IMPLEMENTACION ES EL SIGUIENTE:
#include
#include
using namespace std;
#define TAM1 4 // numero de filas de la matriz cuadrada segun la que utilices
int Buscar( char c, int estado, char tabla[TAM1][TAM1] , int col );
bool Gramatica( string cad );
int main(){
string cad = "abccbbbbbccbbcbc";
if( Gramatica(cad) )
cout << endl << "Cadena aceptada..." << endl << endl;
else
cout << endl <<"Cadena rechazada..." << endl << endl;
return 0;
}
bool Gramatica( string cad ){
/**/
// Tabla para la gramática1 a(b|c)*
static char tabla[TAM1][TAM1]= {
{ '-', 'a', '-', '-'},
{ '-', '-', 'c', 'b'},
{ '-', 'b', '-', 'c'},
{ '-', 'c', 'b', '-'}
};
// Tabla para la gramática2 (b|c)*a
/*static char tabla[TAM1][TAM1]= {
{ '-', '-', '-', '-'},
{ 'a', '-', 'c', 'b'},
{ 'a', 'b', '-', 'c'},
{ 'a', 'c', 'b', '-'}
};*/
// Tabla para la gramática3 a(b|c)+
/*static char tabla[TAM1][TAM1]= {
{ '-', 'a', '-', '-', '-', '-', '-'},
{ '-', '-', 'b', '-', '-', '-', 'c'},
{ '-', '-', '-', 'b', 'c', '-', '-'},
{ '-', '-', '-', '-', 'b', 'c', '-'},
{ '-', '-', '-', 'b', '-', 'c', '-'},
{ '-', '-', '-', 'c', 'b', '-', '-'},
{ '-', '-', '-', '-', 'c', 'b', '-'}
};*/
// Tabla para la gramática4 (b|c)+a
/*
static char tabla[TAM1][TAM1]= {
{ '-', '-', '-', '-', '-', '-', '-'},
{ '-', '-', 'b', '-', '-', '-', 'c'},
{ '-', '-', '-', 'b', 'c', '-', '-'},
{ 'a', '-', '-', '-', 'b', 'c', '-'},
{ 'a', '-', '-', 'b', '-', 'c', '-'},
{ 'a', '-', '-', 'c', 'b', '-', '-'},
{ '-', '-', '-', '-', 'c', 'b', '-'}
};*/
static int estado = 0; // para a(b|c)* y a(b|c)+
//static int estado = 1; // para (b|c)*a y (b|c)+a
//static bool finales[] = { false, true, true, true };
//static bool finales[] = { false, false, false, true, true, true, false };
static bool finales[] = { true, false, false, false, false, false, false };
int indfin = 1;
string::iterator it = cad.begin();
int pos = -1;
while( it != cad.end() ){
pos = Buscar( *it , estado, tabla, TAM1 );
if( pos == -1 )
return false;
estado = pos;
++it;
}
return pos == -1 ? false : finales[pos];
}
int Buscar( char c, int estado, char tabla[TAM1][TAM1] , int col ){
--col;
cout << "Estado con ("<< c << " , " << estado << " ) = " ;
while( col >= 0 ){
if( c == tabla[estado][col] ){
cout << col << endl;
return col;
}
--col;
}
return col;
}
El codigo no es de mi estilo pero bueno hoy no eh tenido mucho tiempo quizas luego les traiga un buen programa generador de automatas (Y).
>-< ZOIDHACK >-<