Adp

Enviado por Programa Chuletas y clasificado en Matemáticas

Escrito el en español con un tamaño de 3,15 KB

AUTOMATA DE PILA utiliza como memoria una pila de datos y para insertar datos utiliza un procedimiento llamado PUSH 1. incrementar la cima 2. insertar datos POP 1. extraer dato 2. Decrementar la cima. DEFINICION al igual q un AFD cuenta con un flujo de entrada y unmecanismo de control que puede encontrarse en uno de un numero finito de estados y por lo menos uno es de aceptacion. la principal diferencia es que ahora se cuenta con un lugar dond guardar informacion para recuperarla mas tarde. Los simbolos que pueden almacenarse se llaman simbolos de pila y son un conjunto finito que puede incluir el alfabeto de la maquina los simbolos auxiliares y la marca de pila vacia







este proceso se representar con la notasion (p, x, s: q, y) P edo actual X simbolo que se lee de la cadena de entrada S es el simbolo que se extrae de la pila Q es el estado al que se pasa y Y es el simbolo que se inserta en la pila.
DEFINICION FORMAL un automata de pila es una sextupla de la forma ( Q ?, R, , Qo, F) Q conjutno de edos ? alfabeto de la maquina R conjunto de simbolos de pila conjunto de transicion Qo edo inicial F Conjunto de edos de aceptacion


  TEOREMA: para cada AFD existe un automata de pila equivalente DEMOSTRACION dada una gramatica G que representar un AFD construimos un automata de pila de la sig. forma 1. Designe el alfabeto igual al del automata finito y los simbolos de pila como lo terminales y auxiliares de G agregando el simbolo pragma (#) 2 designe los estados del automata como t, p, q, f en dond T edo inicial y F es el unico edo de aceptacion 3 introdusca la transicion (+, ? , ? : p #) 4 Introdusca la transicion (p, ? , ? : q, s) en donde S es el axioma de la gramatica 5. introdusca la transcion de la forma (q, ? , N: q, W) 6. introdusca la transcion de la forma (q, x, x: q , ? ) para cada terminal de X de G, es decir para cada simbolo del alfabeto 7 introdusca (q, ? , #: f, ? )....""METODO DE LAS 3 COLUMAS-CONTENIDO DE LA PILA, RESTO DE LA CADENA, TRANSICION UTILIZADA""

Entradas relacionadas: