Automatas De Pila

Autómatas de Pila

La única diferencia entre un autómata finito indeterminista y uno de pila es que el segundo posee una memoria en forma de pila en la que puede almacenar información para recuperarla más tarde. De modo que los lenguajes aceptados por los autómatas de pila incluyen los lenguajes regulares. Un autómata de pila se define por la séxtupla (S, Σ, Γ, T, ι, F) en la que:

• S es una colección de estados finitos.

• Σ es el alfabeto de la máquina.

• Γ es la colección finita de símbolos de pila. Como convención utilizaremos el símbolo # como indicador de pila vacía.

• T es una colección finita de transiciones. Una transición se define como (p, x, s; q, y) y significa que estando el autómata en el estado p, si lee x de la entrada y s está en la cima de la pila, se extrae s, se inserta y en la cima y se pasa al estado q.

• ι (un elemento de S) es el estado inicial.

• F (un subconjunto de S) es la colección de estados de aceptación.

Teorema 2.1: Para cada autómata de pila que acepte cadenas sin vaciar su pila, existe otro autómata de pila que acepta el mismo lenguaje pero vacía su pila antes de llegar a un estado de aceptación.

Límites de los Autómatas de Pila

Teorema 2.5: Si L es un lenguaje independiente de contexto que contiene un número infinito de cadenas, entonces debe existir en L una cadena de la formasvuwt donde s, v, u, w y t son subcadenas, por lo menos v o w es no vacía y svnuwnt está en L para cada n ∈ N+. Este teorema es también conocido como ellema de bombeo.

Autómata de Pila Determinista: Es un autómata de pila en el cual es aplicable una, y sólo una transición en cualquier instante. Los lenguajes aceptados por estos autómatas se denominan lenguajes independientes del contexto determinista.

Teorema 2.6: Existe un lenguaje independiente del contexto que no es el lenguaje aceptado por ningún autómata de pila determinista.

LÍMITE DE LOS AUTÓMATAS FINITOS DETERMINISTAS

Esta sección tratará de distinguir entre cadenas aceptables y no aceptables por autómatas finitos deterministas.

Definiciones previas

Vamos a definir |w| como la longitud de una cadena (número de símbolos que contiene el cual como se dijo antes podía ser infinito aunque contable).

Dado un alfabeto, S, vamos a considerar todas las cadenas de longitud finita (incluyendo la vacía), a partir de este alfabeto y lo vamos a designar con S*(no confundirlo con el conjunto potencia del alfabeto,

...