Páginas

NIMADRES

Automata en C++

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.

Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

En este autómata nos basamos en la imagen siguiente, la cual muestra el diagrama del autómata con la secuencia de estados, este es un autómata finito determinista, ya no tiene transiciones vacías.
El programa esta hecho en base al ejemplo tal cual.


Este autómata verifica una cadena, si llega al estado 4 significa que la cadena ingresada es un hexadecimal, si el estado termina en 5 significa que es un natural, si termina en 7  es decimal, si termina en 8 es un octal.
Este es solo un ejemplo, ustedes en base a este que esta simple pueden hacer uno mucho mas complejo.

La manera en la que se maneja el programa es muy parecida a la de un analizador léxico ya que regresa que tipo de cadena es, esto lo hice solo para verificar que el programa funciona correctamente.





Eh aquí el Código:


#include <iostream>
#define UDEF -1
using namespace std;
int delta(int estado, char c){
 switch(estado){
          case 0: if(c == '0') return 1;
                  else if((isdigit(c)) and c > '0') return 5;
                  else if(c == '.') return 6;
                  else return UDEF;
          case 1: if(isdigit(c) and c < '8') return 8;
                  else if(c == 'X' or c == 'x') return 2;
                  else if(c == '.') return 6;
                  else return UDEF;
          case 2: if(isxdigit(c)) return 3;
                  else return UDEF;
          case 3: if(isxdigit(c)) return 4;
                  else return UDEF;
          case 4: if(isxdigit(c)) return 3;
                  else return UDEF;
          case 5: if(isdigit(c)) return 5;
                  else if( c == '.') return 6;
                  else return UDEF;
          case 6: if(isdigit(c)) return 7;
                  else return UDEF;
          case 7: if(isdigit(c)) return 7;
                  else return UDEF;
          case 8: if(isdigit(c) and c < '8') return 8;
                  else return UDEF;                  
    }
}

string process(int estado, const char *cadena){
    for(int i = 0;cadena[i] != 0; i++){
        estado = delta(estado,cadena[i]);
        if(estado == UDEF) break;
    }
 if(estado == 4) return "hexadecimal";
 else if(estado == 5) return "natural";
 else if(estado == 7) return "decimal";
 else if(estado == 8) return "octal";
 else return "no valida";
}

string test(const char *cadena){
    int pf = 0; // estado inicial
    string tipo;
    tipo = process(pf,cadena);
    return tipo;
}

int main(){
 string cadena;
 cout << "Ingresa la cadena: ";
 getline(cin,cadena);
 cout << "La cadena es: " << test(cadena.c_str());
 return 0;
}


Si tienen comentarios o sugerencias, no duden en comentar.


5 comentarios: