09:15

00

Temas  Definición de autómata de pila  Autómata de pila determinístico y no determinístico

Objetivo Que el estudiante logre: 1) Identificar conceptos constructivos de la Teoría de la Computabilidad. 2) Definir autómatas de pila.

09:15

11

Autómata • Dispositivo mecánico capaz de procesar cadenas de símbolos. • Dado un lenguaje L definido sobre un alfabeto A y una cadena x arbitraria, determina si x  L o x  L. • Un autómata tiene dos posibles reacciones: SI

Las hileras son reconocidas o aceptadas

Cadena x

Autómata NO Las hileras son rechazadas por el autómata

Lenguaje 09:15

22

Las gramáticas proporcionan un método para generar cadenas de un lenguaje y para reconocer cadenas de un lenguaje se han descripto autómatas de varios tipos. GRAMÁTICAS

Gramáticas no restringidas

Gramáticas sensibles al contexto

09:15

LENGUAJES

AUTÓMATAS

Lenguajes Irrestrictos o recursivamente enumerables (Tipo 0)

Máquinas de Turing

Lenguajes sensibles al contexto (Tipo 1)

Autómatas ligados linealmente

Gramáticas libres de contexto

Lenguajes libres de contexto (Tipo 2)

Gramáticas regulares

Lenguajes regulares (Tipo 3)

Autómatas de pila

Autómatas finitos

33

Un autómata de pila consiste de: 1) Una unidad de control, que es un autómata finito. 2) Una memoria auxiliar que es una cinta semi-infinita con una clase particular de acceso restringido. La memoria de los autómatas de pila los hace más poderosos que los autómatas finitos. El acceso restringido a la memoria auxiliar es del tipo LIFO (last input first output). Tal memoria se denomina almacén pushdown o pila.

a b Cabeza lectora

a b b a q0 q1

qn

 

Control

q2

qi

q4 09:15

Cinta de entrada

q3

Pila 44

Un autómata de pila (pushdown automata) es:

A = (Q, ,, ,q0 ,z0 ,F) donde:   

  



Q es un conjunto no vacío de estados.  es el alfabeto de entrada, no vacío.  es el alfabeto de la pila, no vacío. q0  Q es el estado inicial. F  Q es el conjunto de estados finales.  es la función de transición directa. Es una proyección: Q x (  ) x  en subconjuntos finitos de Q x *. z0 : símbolo inicial de la pila.

Una configuración de un autómata de pila es una tripla c = (q , a , z) con q Q, a  * , z  *; q es el estado actual, a es el elemento a considerar de la hilera de entrada y z es el contenido de la pila. 5

09:15

5

Entrada no procesada a

Entrada Unidad de control en estado q

q

z

Pila

Funcionamiento o movimientos atómicos: Existen dos clases : 1) (q,a,z) = (p,w) donde: q : estado actual. a : símbolo de la hilera de entrada. z : símbolo del tope de pila. p : próximo estado. w : símbolo que se deja en el tope de pila. Al realizar el movimiento atómico la unidad de control pasa al estado p, el símbolo de entrada a se procesa y el símbolo z del tope de pila se reescribe como la hilera w  *. • Si w =  se borra, la pila pierde el primer símbolo de arriba. • Si |w| = 1, z se reemplaza por otro símbolo, posiblemente el mismo. • Si |w| > 1 se añaden símbolos a la pila.

09:15

66

Entrada no procesada a

Entrada Unidad de control en estado q

q

z

2) (q,,z) = (p,w) Al realizar este movimiento no se procesa ningún símbolo de entrada (la cabeza de entrada no se mueve). El autómata de pila puede cambiar de estado y modificar el contenido de la pila.

Pila

09:15

77

a

,

b

Símbolo que se toma de la hilera de entrada

a

/

Símbolo de tope de pila

b

Símbolo que se carga en el tope de pila

Símbolo anterior al que se carga

El símbolo  a la derecha de la barra, como único elemento: a, b /  significa que se borra de la pila el elemento que se encuentra como tope de pila. El símbolo  a la izquierda de la barra significa fin de la hilera de entrada. L(G) = { an bn / n ≥ 1} a,a/aa

q0

a,z0/az0 09:15

q1

A = ({q0 ,q1 ,q2 ,q3}, {a,b}, {z0 ,a},,q0 ,z0 ,{q3 }) b,a/

b,a/

q2

,z0/z0

q3

(q0 ,a,z0 ) = (q1 ,a z0 ) (q1 ,a,a) = (q1 ,a a) (q1 ,b,a) = (q2 ,) (q2 ,b,a) = (q2 ,) (q2 ,,z0 ) = (q3 ,z0)

88

Los autómatas de pila son no determinísticos, si para algún: (q,a,z) Q x ( ) x , |(q,a,z)| > 1 Un autómata de pila es determinístico si |(q,a,z)| ≤ 1. Ejemplo de Autómata de Pila Determinístico L = {xcx-1 / x {a,b}*} un conjunto de palíndromas con marcador central c. A = ({q0 , q1 , q2}, {a,b,c}, {a,b,z0 }, , q0 , z0 , {q2}) (q0 ,a,z0 ) = (q0 ,a z0 ) (q0 ,b,z0 ) = (q0 ,b z0 ) (q0 ,a,a) = (q0 ,a a) (q0 ,b,b) = (q0 ,b b) (q0 ,a,b) = (q0 ,a b)

(q0 ,b,a) = (q0 ,b a) (q0 ,c,z0 ) = (q1 ,z0 ) (q0 ,c,a) = (q1 ,a) (q0 ,c,b) = (q1 ,b) (q1 ,a,a) = (q1 ,) (q1 ,b,b) = (q1 , ) (q1 , ,z0 ) = (q2 ,z0 )

a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba

q0

09:15

c,z0/z0 c,a/a c,b/b

a,a/

b,b/

q1

,z0/z0

q2 99

Ejemplo de Autómata de Pila No Determinístico L = {xx-1 / x {a,b}*} un conjunto de palíndromas sin marcador central.

A = ({q0 , q1 , q2}, {a,b}, {a,b,z0 }, , q0 , z0 , {q2}) (q0 ,a,z0 ) = (q0 ,a z0 ) (q0 ,b,z0 ) = (q0 ,b z0 ) (q0 ,a,a) = (q0 ,a a) (q0 ,b,b) = (q0 ,b b) (q0 ,a,b) = (q0 ,a b)

a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba

q0

a,a/  b,b/ 

a,a/

b,b/

q1

,z0/z0

q2

,z0/z0

Es no determinístico debido a: (q0 ,a,a) = {(q0 ,a a), (q1 ,)} (q0 ,b,b) = {(q0 ,b b), (q1 , )} No siempre es posible, dado un autómata de pila no determinístico, encontrar un autómata de pila determinístico que acepte el mismo lenguaje. 09:15

10 10



El AP tiene más poder que el autómata finito.

 La memoria (dada por la pila) es de acceso limitado, para acceder a un cierto dato es necesario borrar los anteriores. Esto impide, por ejemplo, reconocer el lenguaje: L(G) = {anbncn / n ≥1}  Se ve entonces la necesidad de disponer otro modelo computacional, que se presenta como otro tipo de autómata, cuya memoria no tenga esas limitaciones. Este modelo es la Máquina de Turing.

 Cada tipo de autómata definido, incluye al anterior como caso particular.

09:15

11 11