04-AutomatasPila-2015

Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar

El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de laComputabilidad– Transparencias de Clase”. Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur

1

Teoría de la Computabilidad

Teoría de la Computabilidad

2015

Departamento de Cs. e Ing. de la ComputaciónUniversidad Nacional del Sur

Bahía Blanca, Argentina

Módulo 4:Módulo 4:Autómatas a PilaAutómatas a Pila

2

Autómatas a Pila (AP)Autómatas a Pila (AP)

Hemos visto que los Lenguajes Regulares (Tipo 3) son generables por Gramáticas Regulares, y reconocibles por Autómatas Finitos.

Nos concentraremos ahora en los Lenguajes Libres de Contexto (o tipo 2).

Veremos un dispositivo que reconoce lenguajes LC llamado Autómata a Pila (en inglés Pushdown automaton)

Hemos visto que los Lenguajes Regulares (Tipo 3) son generables por Gramáticas Regulares, y reconocibles por Autómatas Finitos.

Nos concentraremos ahora en los Lenguajes Libres de Contexto (o tipo 2).

Veremos un dispositivo que reconoce lenguajes LC llamado Autómata a Pila (en inglés Pushdown automaton)

3

Autómatas a Pila (AP) - Esquema generalAutómatas a Pila (AP) - Esquema general

a b c d e f ......

Control de Estados

Pila de SímbolosPila de

Símbolos

El AF posee ahora una estructura de datos auxiliar...

El AF posee ahora una estructura de datos auxiliar...

..es capaz de apilar o desapilar símbolos en una pila

..es capaz de apilar o desapilar símbolos en una pila

La pila le da mayor poder al formalismo, pues el autómata ahora puede “recordar” lo leído en la cinta...La pila le da mayor poder al formalismo, pues el autómata ahora puede “recordar” lo leído en la cinta...

4

Autómatas a Pila (AP) - Esquema generalAutómatas a Pila (AP) - Esquema general

a b c d e f ......

Control de Estados

a

Pila de SímbolosPila de

Símbolos

Los cambios de estado son definidos ahora por el símbolo leído en la cinta, y por el tope de la pila.

Los cambios de estado son definidos ahora por el símbolo leído en la cinta, y por el tope de la pila.

Además de cambiar de estado, en la transición podremos agregar o quitar elementos de la pila...Además de cambiar de estado, en la transición podremos agregar o quitar elementos de la pila...

5

Autómata a Pila (Pushdown automaton)Autómata a Pila (Pushdown automaton)

Def.: Un autómata a pila determinista (APD) P es una6-tupla (S, , , , s0 , F), donde:

• S es un conjunto finito de estados, S Ø.• es un alfabeto de entrada.• es el alfabeto de la pila.• : S x { {}} x * S x *• s0 S es el estado inicial del APD.• F S es el conjunto de estados finales o

aceptadores.

Observación: notar que hay alfabeto de entrada y alfabeto de pila . Eventualmente pueden ser iguales.Observación: notar que hay alfabeto de entrada y alfabeto de pila . Eventualmente pueden ser iguales.

• es el alfabeto de la pila.• : S x { {}} x * S x *

6

Notación. Conceptos ImportantesNotación. Conceptos Importantes

(s0, b, a) = (s1, ba)(s0, b, a) = (s1, ba)

estado actualestado actual

símbolo leídosímbolo leído

símbolo en tope de pilasímbolo en tope de pilanuevo estadonuevo estado

acción sobre la pilaacción sobre la pila

a b a a ......

S0 a

a b a a ......

S1 ab



7

ConfiguraciónConfiguración

Def.: Sea P=(S, , , , s0 , F) un APD. Unaconfiguración es una terna (s,w,) S x *x *

Representa el estado global del APD P.s = estado en cursow = parte aún no leída de la cadena = contenido de la pila (símbolo más a la izq en es el tope de pila; inicialmente = )

Si w = , entenderemos que la cadena fue leída (o sólo restan acciones que no consumen caracteres)

Representa el estado global del APD P.s = estado en cursow = parte aún no leída de la cadena = contenido de la pila (símbolo más a la izq en es el tope de pila; inicialmente = )

Si w = , entenderemos que la cadena fue leída (o sólo restan acciones que no consumen caracteres)

(s0, w, )(s0, w, )Estado inicial s0: La pila está vacía, y toda la cadena w está por ser procesada.

Estado inicial s0: La pila está vacía, y toda la cadena w está por ser procesada.

8

TransiciónTransición

Def.: Una transición de P es representada con unarelación binaria “|-” entre configuraciones: (s,aw,z) |-(s’,w,) si (s,a,z)= (s’, ), donde s,s’S; a{},w* ; z, , *.

Una transición indica la evolución del autómata.

Si a esto determina que si la situación de origen es estado s, símbolo actual a, y símbolo en tope de pila = z, entonces se pasa a estado s’, se desplaza la cabeza lecto-escritora un lugar a derecha, y el tope de pila se reemplaza con .

Si = , entonces se dice que P está desapilando.


Si a esto determina que si la situación de origen es estado s, símbolo actual a, y símbolo en tope de pila = z, entonces se pasa a estado s’, se desplaza la cabeza lecto-escritora un lugar a derecha, y el tope de pila se reemplaza con .

Si = , entonces se dice que P está desapilando.

9

Transición. -MovimientosTransición. -Movimientos


Si a= , esto se llama un -movimiento

Si a=, el símbolo actual no es tomado enconsideración, y la cabeza no se mueve. Pero ...elestado puede ser cambiado, y la pila actualizada! Un-movimiento puede ocurrir aún si toda la cadena yaha sido leída.

Def.: Una transición de P es representada con unarelación binaria “|-” entre configuraciones: (s,aw,z) |-(s’,w,) si (s,a,z)= (s’, ), donde s,s’S; a{},w* ; z, , *.

10

Reconocimiento de cadenasReconocimiento de cadenas

Def.: Se dice que una cadena w es aceptada oreconocida por un AP P=(S, , , , s0 , F) si (s0,w, )|–* (sf, , ) para algún sf F.

Definimos el lenguaje aceptado por P comoL(P)={w|w es aceptada por P}.

Por convención, un AP acepta cadenas cuando

1) termina de procesar la cadena de entrada en unestado aceptador, y

2) su pila está vacía.

El AP se detendrá cuando llega a una configuraciónpara la cual la función no ha sido definida, o se haconsumido la cadena de entrada.

Por convención, un AP acepta cadenas cuando

1) termina de procesar la cadena de entrada en unestado aceptador, y

2) su pila está vacía.

El AP se detendrá cuando llega a una configuraciónpara la cual la función no ha sido definida, o se haconsumido la cadena de entrada.

11

Función de Transición: ejemplosFunción de Transición: ejemplos

(s0, b, a) = (s1, ba)(s0, b, a) = (s1, ba)

Si estado actual = S0Si estado actual = S0

y símbolo leído = by símbolo leído = b

y tope de pila = ay tope de pila = aentonces nuevo estado es S1entonces nuevo estado es S1

apilar b sobre la aapilar b sobre la a

(s0, b, ) = (s1, b)(s0, b, ) = (s1, b)



y la pila está vacíay la pila está vacíaentonces nuevo estado es S1entonces nuevo estado es S1

apilar bapilar b

12


(s3, b, a) = (s4, )(s3, b, a) = (s4, )



y tope de pila = ay tope de pila = aentonces nuevo estado es S4entonces nuevo estado es S4

desapilar el tope de la piladesapilar el tope de la pila

a b a a ......

S3 a

a b a a ......

S4



13


(s3, , b) = (s3, )(s3, , b) = (s3, )


sin consumir nada de la cintasin consumir nada de la cinta

y tope de pila = by tope de pila = bentonces nuevo estado es S3entonces nuevo estado es S3

desapilar el tope de la piladesapilar el tope de la pila

a b a a ......

S3 b

a b a a ......

S3

14


(s3, , S) = (s4, [ ])(s3, , S) = (s4, [ ])



y tope de pila = Sy tope de pila = Sentonces nuevo estado es S4entonces nuevo estado es S4

desapilar S y apilar [ ]desapilar S y apilar [ ]

a b a a ......

S3 S

a b a a ......

S4 ][

15


(s3, , ) = (s4, )(s3, , ) = (s4, )



y la pila está vacía,y la pila está vacía,entonces nuevo estado es S4entonces nuevo estado es S4

mantenemos la pila vacíamantenemos la pila vacía

Ocasionalmente será una acción que sirve para llegar aun estado final o aceptador.

Ejemplo: supongamos que s4 es un estado final.Entonces la configuración a la que se arriba después dela transición anterior es de aceptación, esto es (s4, , ).

Ocasionalmente será una acción que sirve para llegar aun estado final o aceptador.

Ejemplo: supongamos que s4 es un estado final.Entonces la configuración a la que se arriba después dela transición anterior es de aceptación, esto es (s4, , ).

16

Ejemplo 1 Ejemplo 1

Desarrollar un AP para L = {0n1n|n0}.

Sea P=(S, , , , s0 , F) un AP, donde

S= {s0,s1,s2,s3}, = {0,1}, = {0}, F= {s3}

Desarrollar un AP para L = {0n1n|n0}.

Sea P=(S, , , , s0 , F) un AP, donde

S= {s0,s1,s2,s3}, = {0,1}, = {0}, F= {s3}

Idea: P copia los ‘0’ de la cadena de entrada en la pila, y luego desapila un ‘0’ por cada ‘1’ leído. Las principales operaciones del AP pueden definirse como:

Idea: P copia los ‘0’ de la cadena de entrada en la pila, y luego desapila un ‘0’ por cada ‘1’ leído. Las principales operaciones del AP pueden definirse como:

(s0, , ) = (s3, )

(s0, 0, ) = (s1, 0)

(s1, 0, 0 ) = (s1, 00)

(s1, 1, 0 ) = (s2, )

(s2, 1, 0 ) = (s2, )

(s2, , ) = (s3, )

(s0, , ) = (s3, )

(s0, 0, ) = (s1, 0)

(s1, 0, 0 ) = (s1, 00)

(s1, 1, 0 ) = (s2, )

(s2, 1, 0 ) = (s2, )

(s2, , ) = (s3, )

17

Ejemplo 1 (cont.)Ejemplo 1 (cont.)

De s0 con cadena y pila vacía, se pasa a s3

De s0 con cadena y pila vacía, se pasa a s3

Desde s0 al leer 0 y tener pila vacía, paso a s1 y apilo 0Desde s0 al leer 0 y tener pila vacía, paso a s1 y apilo 0

Desde s1 al leer 0 y c/ tope de pila un 0, sigo en s1 y apilo 0Desde s1 al leer 0 y c/ tope de pila un 0, sigo en s1 y apilo 0

Desde s1 al leer 1 y con tope de pila un 0, paso a s2 y desapiloDesde s1 al leer 1 y con tope de pila un 0, paso a s2 y desapilo

En s2 al leer 1 y tener en tope pila un 0, desapiloEn s2 al leer 1 y tener en tope pila un 0, desapilo

En s2 al leer cadena. vacía y tener pila vacía, paso a s3 y aceptoEn s2 al leer cadena. vacía y tener pila vacía, paso a s3 y acepto

(s0, , ) = (s3, )(s0, , ) = (s3, )

(s1, 0, 0 ) = (s1, 00)(s1, 0, 0 ) = (s1, 00)

(s0, 0, ) = (s1, 0)(s0, 0, ) = (s1, 0)

(s1, 1, 0 ) = (s2, )(s1, 1, 0 ) = (s2, )

(s2, 1, 0 ) = (s2, )(s2, 1, 0 ) = (s2, )

(s2, , ) = (s3, )(s2, , ) = (s3, )

18


(s0, , ) = (s3, )

(s0, 0, ) = (s1, 0)

(s1, 0, 0 ) = (s1, 00)

(s1, 1, 0 ) = (s2, )

(s2, 1, 0 ) = (s2, )

(s2, , ) = (s3, )

(s0, , ) = (s3, )

(s0, 0, ) = (s1, 0)

(s1, 0, 0 ) = (s1, 00)

(s1, 1, 0 ) = (s2, )

(s2, 1, 0 ) = (s2, )

(s2, , ) = (s3, )

Con la cadena de entrada 0011 en P, resultan las sgtes.transiciones de configuraciones

(s0, 0011, ) |– (s1, 011, 0) |– (s1, 11, 00) |– (s2, 1, 0) |–

|– (s2, , ) |– (s3, , ) 0011 es aceptada

Con la cadena de entrada 0011 en P, resultan las sgtes.transiciones de configuraciones

(s0, 0011, ) |– (s1, 011, 0) |– (s1, 11, 00) |– (s2, 1, 0) |–

|– (s2, , ) |– (s3, , ) 0011 es aceptada

Atención: En otros libros de texto(y en los softwares comoDeuxExMachina) se utilizanconvenciones diferentes pararepresentar Autómatas a Pila...

Atención: En otros libros de texto(y en los softwares comoDeuxExMachina) se utilizanconvenciones diferentes pararepresentar Autómatas a Pila...



19

Ejemplo 2 Ejemplo 2

Desarrollar un AP para

L = {w{a,b}*, donde w tiene igual nro. de a y b}.



Idea:

Apilar la letra si coincide con la del tope, ydesapilarla en caso contrario. Si en la pila quedana’s, indica que hay mayor nro. de a’s que de b’s.

Idea:

Apilar la letra si coincide con la del tope, ydesapilarla en caso contrario. Si en la pila quedana’s, indica que hay mayor nro. de a’s que de b’s.

20


P=(S, , , , s0 , F)

S= {s0,s1},

= {a,b},

F= {s1}

P=(S, , , , s0 , F)

S= {s0,s1},

= {a,b},

F= {s1}

(s0, a, ) = (s0, a)

(s0, a, a ) = (s0, aa)

(s0, a, b ) = (s0, )

(s0, b, ) = (s0, b )

(s0, b, b ) = (s0, bb)

(s0, b, a) = (s0, )

(s0, , ) = (s1, )

(s0, a, ) = (s0, a)

(s0, a, a ) = (s0, aa)

(s0, a, b ) = (s0, )

(s0, b, ) = (s0, b )

(s0, b, b ) = (s0, bb)

(s0, b, a) = (s0, )

(s0, , ) = (s1, )





21

ObservaciónObservación

Puede utilizarse una representación de los AP pormedio de grafos, de forma similar a los autómatasfinitos.

Para esto basta con etiquetar los arcos no sólocon el símbolo que se está procesando, sino con elestado de la pila antes y después de realizar talprocesamiento.

Puede utilizarse una representación de los AP pormedio de grafos, de forma similar a los autómatasfinitos.

Para esto basta con etiquetar los arcos no sólocon el símbolo que se está procesando, sino con elestado de la pila antes y después de realizar talprocesamiento.

22

Autómata a Pila No Determinista (APND)Autómata a Pila No Determinista (APND)

Def.: Un autómata a pila no determinista (APND) P esuna 6-tupla P= (S, , , , s0 , F), donde:

• S es un conjunto finito de estados, S Ø.

• es un alfabeto de entrada.

• es el alfabeto de la pila.

• : S x { {}} x * Partes(S x *)

• s0 S es el estado inicial del APND.

• F S es el conjunto de estados finales oaceptadores.

• : S x { {}} x * Partes(S x *)

23

Ejemplo APNDEjemplo APND

Sea

P=(S, , , , s0 , F)

S= {s0,s1,s2},

= {a,b},

= {a,b},

F= {s2}

Sea

P=(S, , , , s0 , F)

S= {s0,s1,s2},

= {a,b},

= {a,b},

F= {s2}

(s0, a, ) = { (s0, a) }

(s0, b, ) = { (s0, b) }

(s0, a,a) = { (s0, aa), (s1, ) }

(s0, a, b ) = { (s0, ab) }

(s0, b, a ) = { (s0, ba ) }

(s0, b, b) = { (s0, bb), (s1, )}

(s1, a, a ) = { (s1, ) }

(s1, b, b ) = { (s1, ) }

(s1, , ) = { (s2, ) }

(s0, a, ) = { (s0, a) }

(s0, b, ) = { (s0, b) }

(s0, a,a) = { (s0, aa), (s1, ) }

(s0, a, b ) = { (s0, ab) }

(s0, b, a ) = { (s0, ba ) }

(s0, b, b) = { (s0, bb), (s1, )}

(s1, a, a ) = { (s1, ) }

(s1, b, b ) = { (s1, ) }

(s1, , ) = { (s2, ) }

Diseñar un APND P para

L={wwr|w {a,b}+}

Diseñar un APND P para

L={wwr|w {a,b}+}

24

Dos secuencias posiblesDos secuencias posibles

Ejemplo: consideremos la cadena abbaEjemplo: consideremos la cadena abba

(s0, abba, ) |–(8) (s0, bba, a) |–(12) (s0, ba, ba)

|–(13,opción1) (s0, a, bba) |–(11) (s0, , abba)

En este caso la cadena no es reconocida


|–(13,opción1) (s0, a, bba) |–(11) (s0, , abba)

En este caso la cadena no es reconocida


|–(13,opción2) (s1, a, a) |–(14) (s1, , ) |–(16) (s2, , )

En este caso la cadena es reconocida


|–(13,opción2) (s1, a, a) |–(14) (s1, , ) |–(16) (s2, , )

En este caso la cadena es reconocida



25

L(APND)

Reflexiones sobre APD vs. APNDReflexiones sobre APD vs. APND

L={wwr|w {a,b}+} no puede ser reconocido por un APdeterminista, pero sí por un AP no determinista.L={wwr|w {a,b}+} no puede ser reconocido por un APdeterminista, pero sí por un AP no determinista.

Intuitivamente, vemos que un APND es más “potente”que un AP. Formalmente:Intuitivamente, vemos que un APND es más “potente”que un AP. Formalmente:

Teorema: Los APND tienen mayor poder dereconocimiento de lenguajes que los APD.

L(APD)

26

AP y Gramáticas Libres de ContextoAP y Gramáticas Libres de Contexto

¿Que relación existe entre los autómatas a pila y las gramáticas libres de contexto?

¿Que relación existe entre los autómatas a pila y las gramáticas libres de contexto?

Esta equivalencia es sumamente útil al momento deimplementar analizadores sintácticos para lenguajes deprogramación.

Antes de probar formalmente esta equivalencia, daremosalgunas definiciones auxiliares...

Esta equivalencia es sumamente útil al momento deimplementar analizadores sintácticos para lenguajes deprogramación.

Antes de probar formalmente esta equivalencia, daremosalgunas definiciones auxiliares...

RespuestaLos APND reconocen exactamente la clase de

lenguajes generados por las GLC.

RespuestaLos APND reconocen exactamente la clase de

lenguajes generados por las GLC.

27

Definiciones auxiliaresDefiniciones auxiliares

Sea G = (Vn,Vt,S,P) una GLC. Ent. wL(G) sssiw Vt* y existe una derivación

S 1 2 3... w con cadenas i (Vn Vt)+.

Diremos que una derivación es una derivación aizquierda si el símbolo no terminal reemplazado encada paso es el ubicado más a la izquierda.

Diremos que una derivación es una derivación aizquierda si el símbolo no terminal reemplazado encada paso es el ubicado más a la izquierda.

Ejemplo: sea G = (Vn,Vt,S,P), Vn = {S}, Vt = { ], [ } y P ={S [ ], S SS, S [S] }. Según la def. anterior,S SS [ ]S [ ][ ] es una derivación a izq.SSSS[ ][ ][ ] no lo es.

Ejemplo: sea G = (Vn,Vt,S,P), Vn = {S}, Vt = { ], [ } y P ={S [ ], S SS, S [S] }. Según la def. anterior,S SS [ ]S [ ][ ] es una derivación a izq.SSSS[ ][ ][ ] no lo es.

28

Teorema de Equivalencia entre APND y LLCTeorema de Equivalencia entre APND y LLC

Teorema: La clase de lenguajes aceptados porAPND es exactamente la clase de LLC.

La demostración será por doble implicación:

a) Si un lenguaje es LC, entonces es aceptado por unAPND [demostración a continuación]

b) Si un lenguaje es aceptado por un APND, entonceses LC [sin demostración]

La demostración será por doble implicación:

a) Si un lenguaje es LC, entonces es aceptado por unAPND [demostración a continuación]

b) Si un lenguaje es aceptado por un APND, entonceses LC [sin demostración]

29

Si L es LLC L es aceptado por APNDSi L es LLC L es aceptado por APND

Sea G = (Vn,Vt,S,P) una GLC. Construiremos un AP P talque L(G)=L(P).

El autómata P tendrá sólo dos estados: s0 y s1. Luego delprimer movimiento, P estará siempre en estado s1. Psimulará las derivaciones de la cadena de la gramática,usando Vn Vt como alfabeto de la pila.

Sea G = (Vn,Vt,S,P) una GLC. Construiremos un AP P talque L(G)=L(P).

El autómata P tendrá sólo dos estados: s0 y s1. Luego delprimer movimiento, P estará siempre en estado s1. Psimulará las derivaciones de la cadena de la gramática,usando Vn Vt como alfabeto de la pila.

Definiremos P = ({s0,s1}, Vt , Vn Vt , , s0, {s1}), con:

(s0 , , ) = {(s1,S)} (apila S, símbolo inicial de G)

(s1 , , 1) {(s1,2)} para cada regla 1 2 P.

(s1 , a, a) = {(s1, )} para cada aVt.

Definiremos P = ({s0,s1}, Vt , Vn Vt , , s0, {s1}), con:

(s0 , , ) = {(s1,S)} (apila S, símbolo inicial de G)

(s1 , , 1) {(s1,2)} para cada regla 1 2 P.

(s1 , a, a) = {(s1, )} para cada aVt.

30

Si L es LLC L es aceptado por APNDSi L es LLC L es aceptado por APND

o bien se reemplaza el no terminal A del tope de lapila por la parte derecha de la producción que lecorresponde,

o bien se desapila el símbolo del tope si coincidecon la entrada.

o bien se reemplaza el no terminal A del tope de lapila por la parte derecha de la producción que lecorresponde,

o bien se desapila el símbolo del tope si coincidecon la entrada.

El Autómata comenzará apilando S, el símbolo inicialde G, y pasa a estado s1. En cada paso que sigue:El Autómata comenzará apilando S, el símbolo inicialde G, y pasa a estado s1. En cada paso que sigue:

Las transiciones hacen la “mímica” de una derivación a izquierda en caso que la cadena de entrada pertenezca al lenguaje.

Si L(G), basta agregar el estado inicial de P a su conjunto de estados finales.

Las transiciones hacen la “mímica” de una derivación a izquierda en caso que la cadena de entrada pertenezca al lenguaje.

Si L(G), basta agregar el estado inicial de P a su conjunto de estados finales.



31

Ejemplo LLCAPNDEjemplo LLCAPND

Sea la gramática G=(Vn,Vt,S,P), con Vn={S}, Vt={[,]}, P={ S[ ], SSS, S[S]}.

Intentaremos usar el teorema para construir un APNDque reconozca este lenguaje.

Sea la gramática G=(Vn,Vt,S,P), con Vn={S}, Vt={[,]}, P={ S[ ], SSS, S[S]}.

Intentaremos usar el teorema para construir un APNDque reconozca este lenguaje.

Sea P= (K,,,,s0,F)con

K={s0, s1},={[,]},={ S, [, ] } yF={s1 }.

Sea P= (K,,,,s0,F)con

K={s0, s1},={[,]},={ S, [, ] } yF={s1 }.

(s0, , ) = { (s1, S) }

(s1, , S ) = { (s1, [ ]) }

(s1, , S ) = {(s1, SS)}

(s1, , S ) = {(s1,[S] )}

(s1, [, [ ) = {(s1, )}

(s1, ], ]) = {(s1, )}

(s0, , ) = { (s1, S) }

(s1, , S ) = { (s1, [ ]) }

(s1, , S ) = {(s1, SS)}

(s1, , S ) = {(s1,[S] )}

(s1, [, [ ) = {(s1, )}

(s1, ], ]) = {(s1, )}32

Ejemplo LLCAPND (cont.)Ejemplo LLCAPND (cont.)

(s0, [ ] [ ], )

|– (s1, [ ] [ ], S )

|– (s1, [ ] [ ], SS )

|– (s1, [ ] [ ], [ ]S )

|– (s1, ] [ ], ]S )

|– (s1, [ ], S )

|– (s1, [ ], [ ])

|– (s1, ], ])|– (s1, , )

(s0, [ ] [ ], )

|– (s1, [ ] [ ], S )

|– (s1, [ ] [ ], SS )

|– (s1, [ ] [ ], [ ]S )

|– (s1, ] [ ], ]S )

|– (s1, [ ], S )

|– (s1, [ ], [ ])

|– (s1, ], ])|– (s1, , )

(s0, , ) = { (s1, S) }

(s1, , S ) = { (s1, [ ]) }(s1, , S ) = {(s1, SS)}(s1, , S ) = {(s1,[S] )}

(s1, [, [ ) = {(s1, )}

(s1, ], ]) = {(s1, )}

(s0, , ) = { (s1, S) }

(s1, , S ) = { (s1, [ ]) }(s1, , S ) = {(s1, SS)}(s1, , S ) = {(s1,[S] )}

(s1, [, [ ) = {(s1, )}

(s1, ], ]) = {(s1, )}

¿ Acepta la cadena [ ][ ] ?¿ Acepta la cadena [ ][ ] ?

cadena [ ][ ]

Documents

04-AutomatasPila-2015