Automata de pila

Solo disponible en BuenasTareas
  • Páginas : 2 (280 palabras )
  • Descarga(s) : 0
  • Publicado : 14 de julio de 2010
Leer documento completo
Vista previa del texto
AUTOMATAS DE PILA
Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadenaconstituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Una maquina de este tipo se representa de lasiguiente forma:

Funciona bajo el principio PEUS: Primero en Entrar, Último en Salir. Sea Q un conjunto de estados, sea T el alfabeto de entrada y sea V unalfabeto de pila. La función de transición es de la forma, donde la relación se interpreta como sigue: ``Si se está en el estado q, arriba el símbolo a y en eltope de la pila está el símbolo b entonces se pasa al estado p y se empila la palabra ''. Un autómata de pila reconoce a una palabra si, tras haberla leído,termina con su pila vacía.
La principal diferencia entre los autómatas finitos y los autómatas de pila es que los autómatas de pila cuentan con una pila endonde pueden almacenar información para recuperarla más tarde.

Formalmente un autómata de pila es una séxtupla de la forma (S,,,T,i,F) donde:
S: es unacolección finita de estados |
: es el alfabeto de la maquina |
: es la colección finita de símbolos de pila |
T: es una colección finita de transiciones |i: (es un elemento de S) es el estado inicial |
F: (es un subconjunto de S) es la colección de estados de aceptación |

Bibliografías:http://148.202.148.5/cursos/cc209/teoriacomp/MODULO_4/Teoria_4_1.htm
http://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila
http://delta.cs.cinvestav.mx/~gmorales/ta/node14.html
tracking img