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, por ejemplo, en el alfabeto {a,b}, S* será { l, a, b, aa, bb, ab, ba, aaa, aab,...} y P(S)={l, a, b, ab}). Un subconjunto de S* se llama lenguaje (varios subconjuntos denotarán distintos lenguajes).

Si M es un autómata finito determinista (S,S, d,i ,F), la colección de cadenas que acepta constituye un lenguaje con respecto al alfabeto S; Este lenguaje lo representamos con L(M) que se lee "el lenguaje que acepta M". L(M) es la colección de TODAS las cadenas que acepta M (ni más ni menos). El lenguaje que es aceptado por un autómata finito se llama lenguaje regular.

Hay dos tipos especiales de lenguajes regulares:

• La colección de todas las cadenas de longitud finita de un alfabeto ( S* )

• La colección de ninguna cadena, conocido como lenguaje vacío y se representa con Æ (hay que diferenciar el lenguaje con la cadena vacía { l} y el lenguaje que no tiene cadenas {Æ} El primero tiene una cadena y el segundo no tiene ninguna).

cadena vacía lenguaje vacío

Como estamos hablando de conjuntos de cadenas, podemos decir que S* es el conjunto universal, y {Æ } su complementario. Como los dos son lenguajes regulares, entonces podemos generalizar a cualquier lenguaje regular y su complementario,

...