Hoja 12 (18 de Mayo de 2010)

P1: Construye un autómata finito de pila no-determinista (AFPND) que acepta las mismas palabras que genera la gramática de la hoja 11, apartado 2.

Partimos de la siguiente gramática

gramática a transformar

para generar un Autómata de pila a partir de una gramática libre de contexto necesitamos crear un autómata de pila con tres estados.

El estado inicial q0 tiene una transición a q1 leyendo de la cima de la pila el símbolo de pila vaciá, e insertando en la pila el símbolo inicial de la gramática ($),todo esto sin consumir ningún símbolo de la palabra de entrada

en el estado q1 insertamos para cada producción de la gramática una transición consigo mismo en la que se consume el símbolo que genera la producción (parte izquierda $,A,B,I) y se inserta en la pila la derivación (parte derecha A,B,IaI,). Todas estas transiciones no consumen ningún símbolo de la palabra

Para los símbolos terminales se inserta una transición en el estado q1 que consume el un símbolo de la palabra siempre y cuando este símbolo este en el tope de la pila sacándolo de ella.

Finalmente se inserta una transición al estado q2 leyendo el indicador de pila vaciá y volviendo a insertar dicho símbolo, el autómata de pila quedaría definido de la siguiente forma:

Autómata de Pilaverificamos el autómata teniendo en cuenta de que acepta por pila vaciá.

Verificacion automata de pila

Fuente: www.cs.rpi.edu/~drinep/modcomp/class11-12.ppt