Tema: [Aporte] Autómatas en python
Ver Mensaje Individual
  #4 (permalink)  
Antiguo 16/04/2010, 21:08
Avatar de razpeitia
razpeitia
Moderador
  
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años, 9 meses
Puntos: 1360
Respuesta: [Aporte] Autómatas en python
Por si creyeron que dejaría el proyecto acabo de terminar un autómata de pila no determinista.
Push-down automata

Código Python: 
Ver original
  1. class NPDA:
  2.     def __init__(self):
  3.         self.__table = {}
  4.         self.__initial_states = set()
  5.         self.__final_states = set()
  6.         self.__stack = []
  7.         self.__initial_stack_symbol = ""
  8.  
  9.     def add_transition(self, state, symbol, stack_symbol, new_states, stack_action):
  10.         try:
  11.             self.__table[state]
  12.         except KeyError:
  13.             self.__table[state] = {}
  14.             
  15.         try:
  16.             self.__table[state][symbol]
  17.         except KeyError:
  18.             self.__table[state][symbol] = {}
  19.             
  20.         if type(new_states) == str:
  21.             self.__table[state][symbol][stack_symbol] = [(new_states, stack_action)]
  22.         else:
  23.             self.__table[state][symbol][stack_symbol] = zip(new_states, stack_action)
  24.  
  25.     def add_initial_states(self, states):
  26.         if type(states) == str:
  27.             self.__initial_states.update([states])
  28.         else:
  29.             self.__initial_states.update(states)
  30.  
  31.     def add_final_states(self, states):
  32.         if type(states) == str:
  33.             self.__final_states.update([states])
  34.         else:
  35.             self.__final_states.update(states)
  36.  
  37.     def set_initial_stack_symbol(self, symbol):
  38.         self.__initial_stack_symbol = symbol
  39.  
  40.     def __get_new_states_e(self, states):
  41.         visited_states_b = set()
  42.         visited_states_a = states.copy()
  43.         current_states = visited_states_a.difference(visited_states_b)
  44.         while current_states:
  45.             visited_states_b.update(visited_states_a)
  46.             for state in current_states:
  47.                 try:
  48.                     self.__table[state][""]
  49.                 except KeyError:
  50.                     pass
  51.                 else:
  52.                     try:
  53.                         top = self.__stack.pop()
  54.                         for nstate, stack_action in self.__table[state][""][top]:
  55.                             visited_states_a.update([nstate])
  56.                             self.__stack.extend(stack_action[::-1])
  57.                     except IndexError:
  58.                         return set()
  59.                     except KeyError:
  60.                         self.__stack.append(top)
  61.             current_states = visited_states_a.difference(visited_states_b)
  62.         states.update(visited_states_a)
  63.  
  64.     def __get_new_states(self, symbol, states):
  65.         new_states = set()
  66.         for state in states:
  67.             try:
  68.                 self.__table[state][symbol]
  69.             except KeyError:
  70.                 pass
  71.             else:
  72.                 try:
  73.                     top = self.__stack.pop()
  74.                     for nstate, stack_action in self.__table[state][symbol][top]:
  75.                         new_states.update([nstate])
  76.                         self.__stack.extend(stack_action[::-1])
  77.                 except IndexError:
  78.                     return set()
  79.                 except KeyError:
  80.                     self.__stack.append(top)
  81.         return new_states
  82.  
  83.     def evaluate(self, string):
  84.         states = self.__initial_states.copy()
  85.         self.__stack = [self.__initial_stack_symbol]
  86.  
  87.         self.__get_new_states_e(states)
  88.         print self.__stack
  89.         for i in string:
  90.             new_states = self.__get_new_states(i, states)
  91.             self.__get_new_states_e(new_states)
  92.             states = new_states
  93.             if not states:
  94.                 break
  95.             print self.__stack
  96.             
  97.         return bool(states.intersection(self.__final_states))
  98.  
  99.     def print_npda(self):
  100.         print "Table"
  101.         for state in self.__table:
  102.             for symbol in self.__table[state]:
  103.                 for stack_symbol in self.__table[state][symbol]:
  104.                     print "(%s, '%s', '%s') -> %s" % (state, symbol, stack_symbol, self.__table[state][symbol][stack_symbol])
  105.         print "\nInitial States:"
  106.         print self.__initial_states
  107.         print "\nFinal States:"
  108.         print self.__final_states
  109.         print "\nInitial Stack Symbol"
  110.         print self.__initial_stack_symbol
  111.         print ""
  112.  
  113. npda = NPDA()
  114.  
  115. npda.add_initial_states("p")
  116.  
  117. npda.set_initial_stack_symbol("Z")
  118.  
  119. #L(M) = {0^n1^n | n >= 0}
  120. npda.add_transition("p", "0", "Z", "p", "AZ")
  121. npda.add_transition("p", "0", "A", "p", "AA")
  122.  
  123. npda.add_transition("p", "", "Z", "q", "Z")
  124. npda.add_transition("p", "", "A", "q", "A")
  125.  
  126. npda.add_transition("q", "1", "A", "q", "")
  127. npda.add_transition("q", "", "Z", "r", "Z")
  128.  
  129. npda.add_final_states("r")
  130.  
  131. #npda.print_npda()
  132.  
  133. l = ["01", "001", "0011", "", "00", "0111", "1111111"]
  134. for i in l:
  135.     print "'%s' %s" % (i, npda.evaluate(i))