Automata Finito Determinista

Sup dude! Mi unico objetivo de este post es hacer más sencillo y accesible la comprensión de los Automatas Finitos, me hubiese gustado encontrar un post asi para hacer mi tarea (^_^).

Tome esto de wikipedia:

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.  Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

Esencialmente consiste en un algoritmo que recibe como entradas un autómata, y una palabra (conjuto de caracteres); y que devuelva como resultado, si la palabra es reconocida o no por el autómata.

Bien hice esto para mi materia de Compiladores de UAM AZC y vaya que se me hizo bastante confuso al principio por eso es que dejo este codigo tomando la filosofia GNU (GNU Free Documentation License) so este trabajo es completamente libre, pudiendo ser copiado, redistribuido, modificado e incluso vendido ( jaja dudo que alguien pague por esto! ) siempre y cuando el material se mantenga bajo los términos de esta misma licencia (GNU GFDL).

Este Automata borra los espacios en blanco de un codigo en C guardado en un archivo “Entrada.txt” y borra los comentarios deacuerdo a la tabla de transicion que este contenida en un archivo “tabla.txt”,  en mi caso use la matriz siguiente, para el automata (figura) :

Automata Finito para comentarios tipo C

Solo que la tabla de transiciones que implemente comienza en el estado cero ( q =0 ) al estado q = 4 como estado final en lugar de ir del estado 1 al estado 5 como en la figura.

1 0 0 0 0
1 2 0 0 0
2 3 2 0 0
4 3 2 0 0
4 0 0 0 0

#include <iostream>
#include <fstream>
using namespace std;

void SkipWS(void);
void SkipC(void);
int main(){

SkipWS();
SkipC();
return 0;
}

void SkipWS(void){
char d[10000];

ifstream in(“Entrada.txt”);
ofstream o(“out.txt”);

if (!in) cout<<“ERROR! nothing to do”;

while(in){
in >> d;
for(int i = 0; d[i] != 0;++i){
if(d[i] != 32 )
o<<d[i]; }}
in.close();
o.close();
}
void SkipC(void){

char a[10000];
ifstream e(“out.txt”);
//ofstream s(“sal.txt”);

cout<<endl;
if(!e) cout<<“ERROR! nothing to do”;
while(e){ e>>a; }
cout<<a<<endl;
e.close();

int Q=5,A=5;
int F[Q][A];
ifstream b(“tabla.txt”);
if(!b) cout<<“ERROR! nothing to do”;
cout<<“Tabla Transicion para Comentarios:”<<endl;
while(b){
for(int i=0;i<Q;i++){
for(int j=0;j<A;j++){
b >> F[i][j]; } } }
// imprimir matriz
for (int i=0;i<Q;i++){
for (int j=0;j<A;j++){
cout<< F[i][j]<<” “;}
cout<<endl; }
b.close();
int q=0,j;

for(int i=0;a[i]!=0;i++){
if(a[i] == ‘/’) j=0;
else if(a[i] ==’*’) j=1;
else j=2;
q=F[q][j];

if(F[q][j]==0)
cout<<a[i];
}
cout<<endl;
cout<<endl;
//s.close();
}

Definitivamente no es tu tarea pero espero y te sirva.. bytes!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s