Leer Ensayo Completo

Automatas De Pila

Categoría: Temas Variados

Enviado por: yeisonua1973 01 octubre 2012

Palabras: 1641 | Páginas: 7

CIENCIAS DE LA COMPUTACION I 2006

AUT?"MATAS DE PILA

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.

Autómata de pila reconocedor determinístico

APD=<E, A , P, d, e0, Z0, F>

E: Conjunto finito de estados,

A: Alfabeto o conjunto finito de símbolos de la cinta de entrada,

P: Alfabeto o conjunto finito de símbolos de la Pila. PÇA= Æ

d: función de transición de estados

e0: Estado inicial e0 Î E.

Z0: Símbolo distinguido Z0 Î P

F: Conjunto de estados finales o estados de aceptación. F Í E.

La función de transición definida como: d:E x ( A È{e}) x P ® E x P*

1) d( ei , a, X) =( ej , a)

2) d( ei , e, X) =( ej , a) donde a Î A; X Î P; a Î P* ; ei , ej Î E.

Nota: Si existe transición de tipo (2), sólo se garantiza que AP es determinístico si

&quot; s Î A, d( ei , s, X) está indefinida.

Descripción instantánea

Una configuración de un AP es una tripla <e ,s ,p> donde e: estado_actual; s: cadena de entrada ...

Leer Ensayo Completo