Automatas de pilas - Apuntes 1-3 PDF

Preview

Summary

Escoto Gomez Luis DanielI Definición y características de lo que es un autómata de pila A. Definición: Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto determinada si esa cadena pertenece al ...

Description

Escoto Gomez Luis Daniel

1

Autómata de pila 

II Define la forma en que se relaciona o ejecuta las gramáticas de entrada que es capaz de ejecutar. I Definición y características de lo que es un autómata de pila A. Definición: Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto determinada si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce a un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la jerarquía de Chomsky

Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x. B.

Características

Las características de los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un automata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un numero finito de estados. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos pueden ser insertados o extraídos de la pila.

...