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.

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.

Gramáticas Independientes del Contexto

Las gramáticas independientes del contexto se diferencian de las gramáticas regulares en que el lado derecho de las reglas de reescritura no tiene restricciones.

Lenguaje independiente del contexto: Son los lenguajes generados por las gramáticas independientes del contexto.

Teorema 2.2: Para cada gramática G independiente del contexto, existe un autómata de pila M tal que L(G)=L(M).

Teorema 2.3: Para cada autómata de pila M, existe una gramática G independiente del contexto tal que L(M)=L(G).

Forma Normal de Chomsky: Decimos que una gramática tiene la forma normal de Chomsky si para todas sus reglas de reescritura su lado izquierdo está formado por un no terminal y su lado derecho está formado por un terminal o dos no terminales. Una gramática de este tipo no puede generar la cadena vacía.

Teorema 2.4: Si L es un lenguaje independiente del contexto que no tiene la cadena vacía, entonces existe una gramática G independiente del contexto tal que L(G)=L y G tiene la forma normal de Chomsky.

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 forma svuwt donde s, v, u, w y t son subcadenas, por lo menos v o w es no vacía y svⁿuwⁿt está en L para cada n ∈ N⁺. Este teorema es también conocido como el lema 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.

Principio de Preanálisis: Técnica que consiste en observar los símbolos siguientes sin leerlos. Es utilizado para la construcción de analizadores sintácticos.

Advertisement