Un poco Geek

Autómata de pila X^n W Y^n

July 11, 2007 12:19 am root Parsing, Programación

No 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;

}

Automata de Pila

Califica el tema: