Observaciones sobre Autómatas a Pila en el software DeusExMachina

Prof. Carlos Iván Chesñevar

Fundamentos de Cs. de la Computación, 1er. Cuat. 2002

La notación usada para las transiciones en autómatas a pila en el software DeusExMachina  (DEM) presenta diferencias con la usada en el curso de FCC.   Se indican a continuación las principales diferencias: 

1. En DEM, hay dos alfabetos claramente diferenciados S (input alphabet)  y  G (stack alphabet).  Estos alfabetos no pueden tener símbolos en común. Ej: para resolver el problema de reconocer el lenguaje L= {0n1n, n>=0}, en DEM se necesita un alfabeto especial para la pila, con símbolos diferentes a 0, 1.
2. En DEM existe un símbolo (#) usado por defecto para indicar “stack vacío”. No obstante, cada vez que se define un autómata a pila es necesario incluir ese símbolo como parte del “stack alphabet”.
3. En DEM, la cadena vacía se la representa como e, mientras que en la notación de FCC se utiliza l.
4. En DEM, las transiciones tienen la forma:

(estado origen,

  símbolo leído,

  secuencia a extraer del stack (pop),

  nuevo estado,

  secuencia a apilar en el stack  (push) ) 

       Nótese que esto es diferente a la notación usada en el apunte de FCC: 

(estado origen,

  símbolo leído,

  secuencia presente en el tope del stack,

  nuevo estado,

  sec. a apilar en el stack  (donde l se usa para indicar “desapilar”)  ) 

Ejemplo: Considérese el autómata a pila asociado a L= {0n1n, n>=0}. Utilizando la notación del apunte, nótese que la función de transición se define como sigue: 

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

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

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

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

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

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

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

Para codificar este autómata en DEM, deben realizarse los siguientes pasos: 

1) Definir primero de todo “input alphabet” y “stack alphabet”. Definir “0” y “1” como parte del input alphabet, y “#”  y “a” como parte del stack alphabet (nótese que elegimos “a” como símbolo para apilar, pero  podríamos haber optado por cualquier otro símbolo que no fuera “0” o “1”). 

2) Definir los estados usando el botón correspondiente. 

3) Definir las transiciones una a una, utilizando el botón correspondiente. Las mismas quedan caracterizadas como sigue (se aclara debajo la interpretación de la tupla). 

(s0 ,      0,  #,  # a ,     s1 ) 

[ de s0, si se lee un 0, y el stack está vacío (#), desapilar el símbolo # y reemplazarlo por # a, y pasar a s1] 

(s1 ,      0,  a,  a a ,     s1 ) 

[ de s1, si se lee un 0, y el stack está tiene en su tope “a”, desapilar el símbolo “a” y reemplazarlo por “a a”, y seguir en s1] 

(s1 ,      1,  a,   e ,        s2 ) 

[ de s1, si se lee un 1, y el stack está tiene en su tope “a”, desapilar el símbolo “a” y reemplazarlo por “e”, y pasar a s2] 

(s2 ,      1,  a,   e ,        s2) 

[ de s2, si se lee un 1, y el stack está tiene en su tope “a”, desapilar el símbolo “a” y reemplazarlo por “e”, y pasar a s2] 

(s2 ,      e,  #,   e ,        s3) 

[ de s2, si se lee cadena vacía, y el stack está vacío (#), desapilar el símbolo “e” y reemplazarlo por “e”, y pasar a s3] 

(s0 ,      e,  #,   e ,        s3) 

[ de s2, si se lee cadena vacía, y el stack está vacío (#), desapilar el símbolo “e” y reemplazarlo por “e”, y pasar a s3]