Tema 2 – Autómatas de Pila y Lenguajes Independientes del Contexto

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.

Tema 1 – Lenguajes Regulares

Autómatas Finitos, Deterministas y No Deterministas

Autómata finito determinista (AFD): Un autómata finito determinista consiste en una quíntupla (S, Σ, δ, ι, F) donde:

• S es un conjunto finito de estados.
• Σ es el alfabeto de la máquina.
• δ es la función de transición de S x Σ a S. δ(p, x) = q si y sólo si la máquina puede pasar de un estado p a un estado q al leer el símbolo x.
• ι es el estado inicial (elemento de S).
• F es el conjunto de estados de aceptación (subconjunto de S).