Autómata de pila X^n W Y^n
July 11, 2007 Parsing, Programación No CommentsNo me voy a liar con conceptos y demás, entonces, miren la wikipedia:
http://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila
Claro cualquier duda también pueden dejarme un comentario y trataré de ayudarle si me es posible :).
Como repaso rápido, un autómata de pila no es más que un algoritmo que aparte de verificar un lenguaje determinado, tiene la posibilidad de poder controlar la aparición de los símbolos definidos en alfabeto de nuestro lenguaje. Para ser más práctico, un ejemplo claro de esto es en los lenguajes de programación, cuando hacemos la llamada a la instrucción if, que tiene sintaxis:
if ( condicion|comparacion ) ;
Como regla básica la instrucción if debe contener un parénesis abierto y otro cerrado, entonces, esta es la posibilidad de un autómata de pila.
Ahora les comparto el código de un programa que determina si la palabra escrita pertenece o no al siguiente lenguaje:
X^n W Y^n
Donde n>=1.
Donde la expresión mínima del lenguaje es:
Expresion a validar:
xwy
SINTAXIS CORRECTA
Las transíciones son:
1) (q0,x,#) -> (q1, )
2) (q1,x,#) -> (q1,a)
3) (q1,w,a) -> (q2, )
4) (q2,y,a) -> (q3,&)
5) (q3,y,a) -> (q3,&)
6) (q3,y,#) -> (q4, )
Más o menos, aclarar que “&” representa quitar un elemento de la pila.
Para compilar con g++:
g++ a202301.cpp -o a202301
Les dejo el código:
/*
Autor: Soul Lost
Descripcion: Lenguaje: x^n w y^n
Donde n>=1.
*/
#include<iostream.h>
#include<stdlib.h>
typedef char cadena[80];
enum alfabeto{x,y,w,FDC};
enum status{mal,bien};
cadena linea;
status result=mal;
alfabeto simbolo;
int pos;
char tope;
//Estructura para llevar el control de la pila
struct nodo{
char smb;
nodo* next;
};
nodo* first=NULL;
int leerCar();
int resultado();
int estado1();
int estado2();
int estado3();
int estado4();
int estado5();
int meter(char);
int sacar();
char obtener();
int main(){
pos=-1;
system("clear");
cout<<"Expresion a validar:"<<endl;
cin>>linea;
meter('#');
estado1();
resultado();
system("sleep 2");
return 0;
}
int resultado(){
if(result) cout<<"SINTAXIS CORRECTA"<<endl;
else cout<<"EXPRESION NO VALIDA"<<endl;
return 0;
}
int leerCar(){
char caracter;
pos++;
caracter=toupper(linea[pos]);
tope=obtener();
if(caracter=='X') simbolo=x;
else if(caracter=='Y') simbolo=y;
else if(caracter=='W') simbolo=w;
else if(caracter=='\0') simbolo=FDC;
return 0;
}
int estado1(){
leerCar();
if(simbolo==x && tope=='#'){
meter('a');
estado2();
}
return 0;
}
int estado2(){
leerCar();
if(simbolo==x && tope=='a'){
meter('a');
estado2();
}
else if(simbolo==w && tope=='a') estado3();
return 0;
}
int estado3(){
leerCar();
if(simbolo==y && tope=='a'){
sacar();
estado4();
}
return 0;
}
int estado4(){
leerCar();
if(simbolo==y && tope=='a'){
sacar();
estado4();
}
else if(simbolo==FDC) estado5();
return 0;
}
int estado5(){
if(tope=='#') result=bien;
delete first;
return 0;
}
int meter(char a){
nodo* nuevo = new nodo;
nuevo->smb=a;
nuevo->next=first;
first=nuevo;
return 0;
}
int sacar(){
if(first==NULL)
return 0;
if(first->next==NULL){
delete first;
}
nodo* actual=first->next;
nodo* temp=first;
first=actual;
delete temp;
return 0;
}
char obtener(){
return first->smb;
}
Califica el tema:
(2 votes, average: 3.5 out of 5)
Loading ...
A probar y jugar 
