Foros del Web » Programando para Internet » Python »

[Aporte] Autómatas en python

 Estas en el tema de [Aporte] Autómatas en python en el foro de Python en Foros del Web. Como un pequeño aporte, libero bajo la licencia GNU v3. Este programa pequeño y no optimizado programa para trabajar con autómatas. Enlace al código Enlace ...
  #1 (permalink)  
Antiguo 25/12/2009, 13:13
Avatar de razpeitia
Moderador
  
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años, 9 meses
Puntos: 1360
[Aporte] Autómatas en python
Como un pequeño aporte, libero bajo la licencia GNU v3. Este programa pequeño y no optimizado programa para trabajar con autómatas.

Enlace al código
Enlace al código mirror
Características:
  • Convierte un autómata No-Determinista a un determinista
  • Evalúa una cadena y determina si pertenece al lenguaje o no

Como veran no es nada formal, falta tratar varias excepciones (como en la función evaluate) y su rendimiento no es el mejor. Pero es excelente para un proyecto final de la universidad.

*Edito: Los link ya han expirado y mi disco duro ha muerto (y con el este proyecto) pero espero hacer una nueva versión algún día.
Última edición por razpeitia; 28/03/2010 a las 18:21
  #2 (permalink)  
Antiguo 10/04/2010, 16:57
Avatar de 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
Ok ese día llego y hoy les muestro una muy reducida y mejorada versión de lo que era mi anterior código.

Código Python: 
Ver original
  1. #coding: utf-8
  2.  
  3. class FSM:
  4.     def __init__(self):
  5.         self.__table = {}
  6.         self.__initial_states = []
  7.         self.__final_states = []
  8.  
  9.     def add_transition(self, state, symbol, new_states):
  10.         """
  11.             state = string
  12.             symbol = string, len = 1
  13.             new_states = list
  14.         """
  15.         if type(new_states) == str:
  16.             self.__table[state] = {symbol: [new_states]}
  17.         else:
  18.             self.__table[state] = {symbol: new_states}
  19.  
  20.     def add_initial_states(self, states):
  21.         """
  22.             state = list or str
  23.         """
  24.         if type(states) == str:
  25.             self.__initial_states.append(states)
  26.         else:
  27.             self.__initial_states.extend(states)
  28.  
  29.     def add_final_states(self, states):
  30.         """
  31.             states = list or str
  32.         """
  33.         if type(states) == str:
  34.             self.__final_states.append(states)
  35.         else:
  36.             self.__final_states.extend(states)
  37.             
  38.     def evaluate(self, string):
  39.         """
  40.             returns:
  41.                 0 -> Match
  42.                 1 -> No match
  43.         """
  44.         states = set(self.__initial_states)
  45.         for c in string:
  46.             new_states = set()
  47.             for state in states:
  48.                 try:
  49.                     self.__table[state][c]
  50.                 except KeyError:
  51.                     pass
  52.                 else:
  53.                     new_states.update(set(self.__table[state][c]))
  54.                 
  55.                 try:
  56.                     self.__table[state][""]
  57.                 except KeyError:
  58.                     pass
  59.                 else:
  60.                     new_states.update(set(self.__table[state][""]))
  61.                     
  62.             states = new_states.copy()
  63.         return states
  64.  
  65.     def print_fsm(self):
  66.         print "Table:"
  67.         print self.__table
  68.         print "\nFinal States:"
  69.         print self.__final_states
  70.         print "\nInitial_states"
  71.         print self.__initial_states
  72.         print ""
  73.  
  74. fsm = FSM()
  75.  
  76. fsm.add_initial_states("q0")
  77.  
  78. fsm.add_transition("q0", "a", "q1")
  79. fsm.add_transition("q1", "a", "q1")
  80. fsm.add_transition("q2", "b", "q2")
  81.  
  82. fsm.add_final_states(("q1", "q0"))
  83.  
  84. fsm.print_fsm()
  85.  
  86. print fsm.evaluate("")
  87. print fsm.evaluate("a")
  88. print fsm.evaluate("aa")
  89. print fsm.evaluate("aaa")
  90. print fsm.evaluate("aaaa")
  91. print fsm.evaluate("aaaaa")
  92. print fsm.evaluate("aaaaaa")
  93. print fsm.evaluate("ba")

Faltan muchos detalles pero se los añadiré después.
Última edición por razpeitia; 10/04/2010 a las 17:54
  #3 (permalink)  
Antiguo 16/04/2010, 10:02
Avatar de 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
Código Python: 
Ver original
  1. #coding: utf-8
  2.  
  3. class FSM:
  4.     def __init__(self):
  5.         self.__table = {}
  6.         self.__initial_states = set()
  7.         self.__final_states = set()
  8.  
  9.     def add_transition(self, state, symbol, new_states):
  10.         """
  11.             state = string
  12.             symbol = string, len = 1
  13.             new_states = list
  14.         """
  15.         try:
  16.             self.__table[state]
  17.         except:
  18.             self.__table[state] = {}
  19.             
  20.         if type(new_states) == str:
  21.             self.__table[state][symbol] = set([new_states])
  22.         else:
  23.             self.__table[state][symbol] = set(new_states)
  24.  
  25.     def add_initial_states(self, states):
  26.         """
  27.             state = list or str
  28.         """
  29.         if type(states) == str:
  30.             self.__initial_states.update([states])
  31.         else:
  32.             self.__initial_states.update(states)
  33.  
  34.     def add_final_states(self, states):
  35.         """
  36.             states = list or str
  37.         """
  38.         if type(states) == str:
  39.             self.__final_states.update([states])
  40.         else:
  41.             self.__final_states.update(states)
  42.  
  43.     def __get_new_states_e(self, states):
  44.         visited_states_a = states.copy()
  45.         visited_states_b = set()
  46.         current_states = visited_states_a.difference(visited_states_b)
  47.         while current_states:
  48.             visited_states_b.update(visited_states_a)
  49.             for state in current_states:
  50.                 try:
  51.                     self.__table[state][""]
  52.                 except KeyError:
  53.                     pass
  54.                 else:
  55.                     visited_states_a.update(self.__table[state][""])
  56.             current_states = visited_states_a.difference(visited_states_b)
  57.         states.update(visited_states_a)
  58.  
  59.     def __get_new_states(self, states, symbol):
  60.         new_states = set()
  61.         for state in states:
  62.             try:
  63.                 self.__table[state][symbol]
  64.             except KeyError:
  65.                 pass
  66.             else:
  67.                 new_states.update(self.__table[state][symbol])
  68.         return new_states
  69.                 
  70.         
  71.     def evaluate(self, string):
  72.         """
  73.             returns:
  74.                 0 -> Match
  75.                 1 -> No match
  76.         """
  77.         states = self.__initial_states.copy()
  78.         self.__get_new_states_e(states)
  79.         for c in string:
  80.             new_states = self.__get_new_states(states, c)
  81.             self.__get_new_states_e(new_states)
  82.             states = new_states
  83.         return bool(states.intersection(self.__final_states))
  84.  
  85.     def print_fsm(self):
  86.         print "Table:"
  87.         for state in self.__table:
  88.             for symbol in self.__table[state]:
  89.                 print "(%s, '%s') -> %s" % (state, symbol, self.__table[state][symbol])
  90.                 
  91.         print "\nFinal States:"
  92.         print self.__final_states
  93.         print "\nInitial_states"
  94.         print self.__initial_states
  95.         print ""
  96.  
  97. fsm = FSM()
  98.  
  99. fsm.add_initial_states("q0")
  100.  
  101. """
  102. #Language a+b*
  103. fsm.add_transition("q0", "a", "q1")
  104. fsm.add_transition("q1", "a", "q1")
  105. fsm.add_transition("q2", "b", "q2")
  106. """
  107.  
  108. #(a* | b*)
  109. fsm.add_transition("q0", "", ["q1", "q2"])
  110. fsm.add_transition("q1", "a", "q1")
  111. fsm.add_transition("q2", "b", "q2")
  112.  
  113.  
  114. fsm.add_final_states(("q1", "q2"))
  115.  
  116. fsm.print_fsm()
  117.  
  118. print fsm.evaluate("") #True
  119. print fsm.evaluate("a") #True
  120. print fsm.evaluate("aa") #True
  121. print fsm.evaluate("aaa") #True
  122. print fsm.evaluate("aaaa") #True
  123. print fsm.evaluate("aaaaa") #True
  124. print fsm.evaluate("aaaaaa") #True
  125. print fsm.evaluate("ba") #False

Acabo de corregir las transiciones epsilon que no funcionaban :P
Última edición por razpeitia; 16/04/2010 a las 11:53
  #4 (permalink)  
Antiguo 16/04/2010, 21:08
Avatar de 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))
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 1 personas


« Tema Anterior | Próximo Tema »


La zona horaria es GMT -6. Ahora son las 21:06.