Automatas de pila
para entender este post deben tener conocimiento previo de que son los lenguajes libres de contexto.
Una automata de pila es como un automata finito, solo que se le agrega una pila , en la que se va agregando y sacando símbolos, es como una memoria que le sirve para recordar símbolos introducidos anteriormente.
se lo puede describir de una manera informal como una maquina abstracta que tiene, una cinta con la cadena de entrada, un cabezal de lectura, y una pila (es una pila, porque va guardando símbolos uno arriba del otro como una pila)
la cinta contiene los símbolos de la cadena de entrada, el cabezal va leyendo los símbolos de entrada, y a cada uno que lee, esta leyendo también el símbolo que esta en el tope la pila.
Pueden ser deterministicos o no deterministicos.
Cinta: una cinta que contiene los símbolos de entrada, osea la cadena.
Mecanismo de control: es la parte que controla al automata. Tiene 2 cabezales de lectura, uno que lee la cinta, y otro que lee la cima de la pila.
en su centro contiene el indicador de estado, el cual se lo puede representar también con un diagrama de estados, como en los automatas finitos.
Pila: es como un vector vertical de datos, en el cual se saca o lee(pop) y se añade símbolos (push)
También se puede hacer otras operaciones ademas de esas, pero lo explicare mas adelante
en la "imagen 1" esta un automata de pila en el estado q0 y leyendo los primeros 2 símbolos, de la cinta y de la pila.
hay varias maneras de definirlo formalmente, pero la siguiente es una:
es una septupla ---> (Q, Σ, Γ, δ, q0, Z0, F)
Q: conjunto de estados
Σ: alfabeto de entrada
Γ: alfabeto de la pila (aca se encuentran símbolos como Z0 , que se usan como marcadores para indicar el fondo de la pila)
δ: función de transición
Z0: es el símbolo inicial de la pila, indica que se llego al fondo de la pila o, que la pila no contiene ningún símbolo del alfabeto de entrada
F: conjunto de estados finales.
- No hay función de salida, la única salida seria la aceptación o rechazo de la cadena.
- Notamos que este tipo de automata tiene cosas en común con los automatas regulares.
(Q, Σ, δ) son los elementos en común, y los nuevos en esta maquina son (Γ, Z0,)
En este caso, en el automata de pila, la función de transición cambia, se le agrega otro símbolo que condiciona el cambio de estado.
En los otros automatas, el cambio de estado dependía del símbolo de entrada y el estado actual. Ahora depende ademas del símbolo en el tope de la pila
osea, depende de estos tres (q , a, x). estos tres son los que también van a determinar el determinismo o no determinismo del automata de pila.
δ: (q , a, x) ------> (p , y)
Esa transición se lee: Mientras el automata se encuentra en el estad "q" y se lee el símbolo de entrada "a" y el símbolo de la pila "x", el automata cambia a otro estado "p", y reemplaza el símbolo "x" por otro símbolo o cadena.
Esta es la parte que mas confunde, ya que la función de transición puede ser como las siguientes...
δ: (q , a, x) ------> (p , λ)
mientras esta en "q", y se lea el símbolo "a" y el "x" en la pila, se pasa al estado "p" y se reemplaza
el símbolo "x" en la pila por la cadena vacía, osea, se borra el símbolo "x" y no se agrega nada. la pila queda con un elemento menos.
o incluso nos podríamos mover al mismo estado "q" y no a otro "p"
δ: (q , a, λ) ------> (p , y)
si se esta en el estado "q" y se lee "a", no importa lo que haya en la pila, se lee la cadena vacía, osea no se saca nada de la pila. Se pasa al estado "q" y sea agrega el símbolo o cadena "y" en el tope, sin eliminar nada de lo que había.
δ: (q , λ, λ) ------> (p , λ)
si se esta en el estado "q" se puede pasar a otro estado sin ingresar nada y sin importar que haya encima de la pila, solo lee la cadena vacía y la reemplaza con otra cadena vacía, dejando la pila invariante y pasando al estado "p"
Este tipo de transición aparece en los automatas de pila no deterministas
δ: (q , λ, λ) ------> (p , y)
Lo mismo que la de arriba, solo que se escribe el simbolo o cadena "y" encima de la pila, sin reemplazar nada anterior
Ahora vamos a ver como podemos representar el siguiente lenguaje infinito no regular aⁿbⁿ
los lenguajes regulares los podíamos definir por medio de expresiones regulares, pero en este caso
este lenguaje se definiría así:
L={ aⁿbⁿ / n>=1}
El lenguaje es igual a: "a" a la N seguido de "b" a la N, tal que N es mayor o igual a 1.
con esto obtendríamos el lenguaje infinito, con cadenas que tienen la misma cantidad de "a's" que de "b's".
usaremos la pila para poder determinar cuantas As ingresamos para detectar la misma cantidad de Bs,y asi poder saber si la cadena pertenece o no al lenguaje.
para saberlo, basta con llenar la pila con todas las As que leemos en la entrada y luego cuando pasamos a leer Bs, vamos eliminando una A por cada B que leemos en la entrada. Si la pila queda vacía y no hay mas símbolos que leer, la cadena sera aceptada, ya sea pasando a un estado de aceptación o considerando que una cadena es aceptada cuando la pila queda vacía.
-se lo puede construir de diferentes maneras, un posible automata que acepte este lenguaje es el siguiente.
Eso es lo que se vería dentro de la Mecanismo de control de la primera imagen 1
Encima de cada flecha hay 3 cosas
a , Z ; AZ
"a" es el símbolo que se lee en la entrada
"Z" es el símbolo que se lee en la pila Notar que Z es el símbolo inicial de la pila, que esta desde el inicio, sin que hayamos leído nada todavía, se utiliza como marca que indica el fondo de la pila, para que en un futuro, sepamos que esta vacía y pasar al estado de aceptación (los símbolos de la pila están en mayúsculas)
"AZ" es la cadena que se inserte en el lugar de "Z". ya que al leer un símbolo de la pila este se elimina obligatoriamente (pop), y como no queremos perder el símbolo que leímos, pues lo volvemos a escribir en la pila, pero ademas, poniendo el símbolo "a" que leímos de entrada en la pila como "A". por lo que nos queda como que escribimos en la pila la cadena AZ (push).
y bueno, las demás transiciones ya sabrán como se comportan porque las explique mas arriba.
Transiciones del automata de la miagen 2:
δ: (q0 , a, Z) ------> (q0 , AZ)
δ: (q0 , a, A) ------> (q0 , AA)
δ: (q0 , b, A) ------> (q1 , λ)
δ: (q1 , b, A) ------> (q1 , λ)
δ: (q1 , λ, Z) ------> (q2 , Z)
Igresemos la cadena w = aaabbb y veamos como se comporta mas a fondo...
estado actual: q0
lee entrada: (a)aabbb
lee pila: (Z)
Buscamos si hay una transicion para el estado en el que estamos y los simbolos que leemos...
δ: (q0 , a, Z) ------> (q0 , AZ)
estado actual: q0
lee entrada: a(a)abbb
lee pila: (A)Z
δ: (q0 , a, A) ------> (q0 , AA)
estado actual: q0
lee entrada: aa(a)bbb
lee pila: (A)AZ
δ: (q0 , a, A) ------> (q0 , AA)
estado acutal: q0
lee entrada: aaa(b)bb
lee pila: (A)AAZ
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaab(b)b
lee pila: (A)AZ
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaabb(b)
lee pila: (A)Z
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaabbb(λ)
lee pila: (Z)
δ: (q1 , λ, Z) ------> (q2 , Z)
Estado actual: q2 de aceptacion
ademas, no hay mas símbolos que leer, estamos leyendo lambda, por lo que la cadena se acepta.
si le hubiéramos ingresado la cadena, por ejemplo, "bbb", el automata, en el estado q0, no tendría camino a donde ir, por lo que se "trabaría", no continuaría, la cadena no seria aceptada.
Ahora, podemos crear un automata equivalente a partir del de la imagen 2, que acepte exactamente el mismo lenguaje, pero esta vez, no por estado de aceptación, sino mas bien, cuando la pila se vacía completamente.
Es muy parecido al anterior, solo que le quitamos el estado de aceptación y en este caso si se fijan en la primera transición, cuando se ingresa una "a" no se reemplaza en la pila por "AZ", sino por una sola "A"- porque no vamos a conservar la "Z", así, cuando eliminemos todo de la pila y no haya mas entradas, lo único que nos indica que la cadena se ha aceptado, es que la pila queda completamente vacía.
Una automata de pila es como un automata finito, solo que se le agrega una pila , en la que se va agregando y sacando símbolos, es como una memoria que le sirve para recordar símbolos introducidos anteriormente.
se lo puede describir de una manera informal como una maquina abstracta que tiene, una cinta con la cadena de entrada, un cabezal de lectura, y una pila (es una pila, porque va guardando símbolos uno arriba del otro como una pila)
la cinta contiene los símbolos de la cadena de entrada, el cabezal va leyendo los símbolos de entrada, y a cada uno que lee, esta leyendo también el símbolo que esta en el tope la pila.
Pueden ser deterministicos o no deterministicos.
Partes de un autómata de pila
Cinta: una cinta que contiene los símbolos de entrada, osea la cadena.
Mecanismo de control: es la parte que controla al automata. Tiene 2 cabezales de lectura, uno que lee la cinta, y otro que lee la cima de la pila.
en su centro contiene el indicador de estado, el cual se lo puede representar también con un diagrama de estados, como en los automatas finitos.
Pila: es como un vector vertical de datos, en el cual se saca o lee(pop) y se añade símbolos (push)
También se puede hacer otras operaciones ademas de esas, pero lo explicare mas adelante
en la "imagen 1" esta un automata de pila en el estado q0 y leyendo los primeros 2 símbolos, de la cinta y de la pila.
 |
| imagen 1 |
Descripción formal
hay varias maneras de definirlo formalmente, pero la siguiente es una:
es una septupla ---> (Q, Σ, Γ, δ, q0, Z0, F)
Q: conjunto de estados
Σ: alfabeto de entrada
Γ: alfabeto de la pila (aca se encuentran símbolos como Z0 , que se usan como marcadores para indicar el fondo de la pila)
δ: función de transición
Z0: es el símbolo inicial de la pila, indica que se llego al fondo de la pila o, que la pila no contiene ningún símbolo del alfabeto de entrada
F: conjunto de estados finales.
Notas...
- No hay función de salida, la única salida seria la aceptación o rechazo de la cadena.
- Notamos que este tipo de automata tiene cosas en común con los automatas regulares.
(Q, Σ, δ) son los elementos en común, y los nuevos en esta maquina son (Γ, Z0,)
En este caso, en el automata de pila, la función de transición cambia, se le agrega otro símbolo que condiciona el cambio de estado.
En los otros automatas, el cambio de estado dependía del símbolo de entrada y el estado actual. Ahora depende ademas del símbolo en el tope de la pila
osea, depende de estos tres (q , a, x). estos tres son los que también van a determinar el determinismo o no determinismo del automata de pila.
δ: (q , a, x) ------> (p , y)
Esa transición se lee: Mientras el automata se encuentra en el estad "q" y se lee el símbolo de entrada "a" y el símbolo de la pila "x", el automata cambia a otro estado "p", y reemplaza el símbolo "x" por otro símbolo o cadena.
Tipos de transiciones del automata a pila
Esta es la parte que mas confunde, ya que la función de transición puede ser como las siguientes...
δ: (q , a, x) ------> (p , λ)
mientras esta en "q", y se lea el símbolo "a" y el "x" en la pila, se pasa al estado "p" y se reemplaza
el símbolo "x" en la pila por la cadena vacía, osea, se borra el símbolo "x" y no se agrega nada. la pila queda con un elemento menos.
o incluso nos podríamos mover al mismo estado "q" y no a otro "p"
δ: (q , a, λ) ------> (p , y)
si se esta en el estado "q" y se lee "a", no importa lo que haya en la pila, se lee la cadena vacía, osea no se saca nada de la pila. Se pasa al estado "q" y sea agrega el símbolo o cadena "y" en el tope, sin eliminar nada de lo que había.
δ: (q , λ, λ) ------> (p , λ)
si se esta en el estado "q" se puede pasar a otro estado sin ingresar nada y sin importar que haya encima de la pila, solo lee la cadena vacía y la reemplaza con otra cadena vacía, dejando la pila invariante y pasando al estado "p"
Este tipo de transición aparece en los automatas de pila no deterministas
δ: (q , λ, λ) ------> (p , y)
Lo mismo que la de arriba, solo que se escribe el simbolo o cadena "y" encima de la pila, sin reemplazar nada anterior
Funcionamiento
Ahora vamos a ver como podemos representar el siguiente lenguaje infinito no regular aⁿbⁿ
los lenguajes regulares los podíamos definir por medio de expresiones regulares, pero en este caso
este lenguaje se definiría así:
L={ aⁿbⁿ / n>=1}
El lenguaje es igual a: "a" a la N seguido de "b" a la N, tal que N es mayor o igual a 1.
con esto obtendríamos el lenguaje infinito, con cadenas que tienen la misma cantidad de "a's" que de "b's".
L={ab, aabb, aaabbb, ......}
usaremos la pila para poder determinar cuantas As ingresamos para detectar la misma cantidad de Bs,y asi poder saber si la cadena pertenece o no al lenguaje.
para saberlo, basta con llenar la pila con todas las As que leemos en la entrada y luego cuando pasamos a leer Bs, vamos eliminando una A por cada B que leemos en la entrada. Si la pila queda vacía y no hay mas símbolos que leer, la cadena sera aceptada, ya sea pasando a un estado de aceptación o considerando que una cadena es aceptada cuando la pila queda vacía.
-se lo puede construir de diferentes maneras, un posible automata que acepte este lenguaje es el siguiente.
 |
| imagen 2: APD por estado final |
Encima de cada flecha hay 3 cosas
a , Z ; AZ
"a" es el símbolo que se lee en la entrada
"Z" es el símbolo que se lee en la pila Notar que Z es el símbolo inicial de la pila, que esta desde el inicio, sin que hayamos leído nada todavía, se utiliza como marca que indica el fondo de la pila, para que en un futuro, sepamos que esta vacía y pasar al estado de aceptación (los símbolos de la pila están en mayúsculas)
"AZ" es la cadena que se inserte en el lugar de "Z". ya que al leer un símbolo de la pila este se elimina obligatoriamente (pop), y como no queremos perder el símbolo que leímos, pues lo volvemos a escribir en la pila, pero ademas, poniendo el símbolo "a" que leímos de entrada en la pila como "A". por lo que nos queda como que escribimos en la pila la cadena AZ (push).
y bueno, las demás transiciones ya sabrán como se comportan porque las explique mas arriba.
Transiciones del automata de la miagen 2:
δ: (q0 , a, Z) ------> (q0 , AZ)
δ: (q0 , a, A) ------> (q0 , AA)
δ: (q0 , b, A) ------> (q1 , λ)
δ: (q1 , b, A) ------> (q1 , λ)
δ: (q1 , λ, Z) ------> (q2 , Z)
Igresemos la cadena w = aaabbb y veamos como se comporta mas a fondo...
estado actual: q0
lee entrada: (a)aabbb
lee pila: (Z)
Buscamos si hay una transicion para el estado en el que estamos y los simbolos que leemos...
δ: (q0 , a, Z) ------> (q0 , AZ)
estado actual: q0
lee entrada: a(a)abbb
lee pila: (A)Z
δ: (q0 , a, A) ------> (q0 , AA)
estado actual: q0
lee entrada: aa(a)bbb
lee pila: (A)AZ
δ: (q0 , a, A) ------> (q0 , AA)
estado acutal: q0
lee entrada: aaa(b)bb
lee pila: (A)AAZ
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaab(b)b
lee pila: (A)AZ
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaabb(b)
lee pila: (A)Z
δ: (q0 , b, A) ------> (q1 , λ)
estado actual: q1
lee entrada: aaabbb(λ)
lee pila: (Z)
δ: (q1 , λ, Z) ------> (q2 , Z)
Estado actual: q2 de aceptacion
ademas, no hay mas símbolos que leer, estamos leyendo lambda, por lo que la cadena se acepta.
si le hubiéramos ingresado la cadena, por ejemplo, "bbb", el automata, en el estado q0, no tendría camino a donde ir, por lo que se "trabaría", no continuaría, la cadena no seria aceptada.
Ahora, podemos crear un automata equivalente a partir del de la imagen 2, que acepte exactamente el mismo lenguaje, pero esta vez, no por estado de aceptación, sino mas bien, cuando la pila se vacía completamente.
 |
| imagen 3: APD por pila vacía |
Autómatas de pila determinista
Hasta ahora, vimos como es un autómata de pila determinista, si se acuerdan, en los autómatas finitos, el no determinismo era cuando, con una entrada, teníamos 2 estados posibles a los que movernos, ya sea porque había dos transiciones con una misma entrada, o por una transición lambda a la cual podíamos movernos en cualquier momento, sin importar la entrada.
En estos autómatas, el determinismo no solo va a estar condicionado por la entrada sino, también por el símbolo de la pila.
para que un autómata de pila sea determinista, tiene que cumplir 2 cosas:
1) hay solo una transición posible para cada combinación de símbolos de la función de transición.
a lo que me refiero es que si tenemos por ejemplo, en el caso del automata anterior: La tripleta (q0, a, Z) le corresponde solo una transición, y esta es (q0, AZ)
2) el segundo caso es que, si estamos en un estado, supongamos q0, si de ese estado sale una transición a la que te podes mover sin necesidad de ingresar ningún símbolo, esa misma transición no debe tener también como condicionante un símbolo que la pila que ya se haya usado para otra transición del estado q0, y viceversa.
ejemplo:
Si del estado "q0" hay una transición "a, Z, AZ", no puede haber otra transición que salga de "q0" y que use "a" y "Z" como condicionante, ni tampoco "λ" y "Z".
tampoco al revés, si hay una con "λ, Z" no puede haber otra con "a, Z"
me explico?
Las dos versiones del automata determinista de arriba cumplen esas condiciones.
Pueden aceptar un lenguaje de 2 maneras: por Pila vacía o Estado de aceptación
Para que un lenguaje pueda ser aceptado por pila vacía, ademas de ser determinista, debe cumplir con la propiedad del prefijo, que ninguna cadena del lenguaje sea prefijo de otra.
por ejemplo la cadena aabb es prefijo de aabbb.
eso implica que, si un lenguaje determinista puede ser aceptado por pila vacía, necesariamente también puede ser aceptado por estado de aceptación.
pero no al revés.
si un lenguaje determinista no posee la propiedad de Prefijo, entonces solo puede ser aceptado por estado, y no se puede armar otro automata que acepte el mismo lenguaje pero por pila vacía
un ejemplo es el lenguaje regular a*.
como es regular, un AP determinista puede aceptarlo, pero solo por estado final, porque vemos que no cumple con la propiedad de Prefijo, algunas de su cadenas son "aa" y "aaa".
para poder ser aceptado por pila vacía, se necesitara construir un AP no determinista que nos cambie de estado en cualquier momento, ya que no sabemos cuando llegamos a la mitad
este automata a pila determinista acepta a* por estado de aceptacion.
como ven, se puede hacer lo que se quiera con la pila, en este caso es irrelevante su uso, porque lo único nos dice si la cadena se acepta es el estado, da igual lo que el automata lee o escribe en ella.
Lenguajes que aceptan los AP Deterministas
Los automatas a pila determinista aceptan todos los lenguajes regulares, pero solo algunos lenguajes independientes de contexto, porque?
vimos en el automata anterior, que para aceptar la cadena, nosotros nos teníamos que mover de un estado a otro. Sabemos cuando movernos al otro estado porque el lenguaje que acepta sigue un patrón, cuando terminas las letras a's cambiamos de estado porque siguen b's
pero y si no hay nada que le diga al automata mientras va leyendo la cadena, cuando tiene que pasar a otro estado?
un ejemplo son los lenguajes de palindromos (cadenas que se leen igual de derecha a izquierda, ejemplo: aabaabaa, 01100110)
el automata no sabría cuando termina la mitad de la cadena, como para moverse a otro estado para empezar a eliminar la pila.
para eso necesitamos una transición δ: (q , λ, λ) ------> (p , λ)
que en en diagrama de estados seria λ, λ; λ
que nos permita movernos a "p" en cualquier momento, sin importar que haya en la pila, y sin eliminar nada, hasta llegar a "p"
Eso convertiría al automata en no determinista.
Veremos como funciona esto mas adelante.
Modos de aceptación de un AP determinista
Pueden aceptar un lenguaje de 2 maneras: por Pila vacía o Estado de aceptación
Para que un lenguaje pueda ser aceptado por pila vacía, ademas de ser determinista, debe cumplir con la propiedad del prefijo, que ninguna cadena del lenguaje sea prefijo de otra.
por ejemplo la cadena aabb es prefijo de aabbb.
eso implica que, si un lenguaje determinista puede ser aceptado por pila vacía, necesariamente también puede ser aceptado por estado de aceptación.
pero no al revés.
si un lenguaje determinista no posee la propiedad de Prefijo, entonces solo puede ser aceptado por estado, y no se puede armar otro automata que acepte el mismo lenguaje pero por pila vacía
un ejemplo es el lenguaje regular a*.
como es regular, un AP determinista puede aceptarlo, pero solo por estado final, porque vemos que no cumple con la propiedad de Prefijo, algunas de su cadenas son "aa" y "aaa".
para poder ser aceptado por pila vacía, se necesitara construir un AP no determinista que nos cambie de estado en cualquier momento, ya que no sabemos cuando llegamos a la mitad
 |
| imagen 4: AP por estado de aceptacion |
este automata a pila determinista acepta a* por estado de aceptacion.
como ven, se puede hacer lo que se quiera con la pila, en este caso es irrelevante su uso, porque lo único nos dice si la cadena se acepta es el estado, da igual lo que el automata lee o escribe en ella.
Comentarios
Publicar un comentario