¿Cómo se implementan los autómatas finitos en el código?

¿Cómo se implementa una dfa o una nfa en el código de Python?

¿Cuáles son algunas buenas maneras de hacerlo en python? ¿Y se usan alguna vez en proyectos del mundo real?

Una forma sencilla de representar un DFA es como un diccionario de diccionarios. Para cada estado, cree un diccionario con las letras del alfabeto y luego un diccionario global con los estados. Por ejemplo, el siguiente DFA del artículo de Wikipedia sobre DFA

introduzca la descripción de la imagen aquí

Puede ser representado por un diccionario como este:

 dfa = {0:{'0':0, '1':1}, 1:{'0':2, '1':0}, 2:{'0':1, '1':2}} 

Para “ejecutar” una dfa contra una cadena de entrada extraída del alfabeto en cuestión (después de especificar el estado inicial y el conjunto de valores de aceptación) es sencillo:

 def accepts(transitions,initial,accepting,s): state = initial for c in s: state = transitions[state][c] return state in accepting 

Usted comienza en el estado inicial, recorre el carácter de cadena por carácter, y en cada paso simplemente busca el siguiente estado. Cuando haya terminado de pasar por la cadena, simplemente verifique si el estado final está en el conjunto de estados de aceptación.

Por ejemplo

 >>> accepts(dfa,0,{0},'1011101') True >>> accepts(dfa,0,{0},'10111011') False 

Para las NFA, puede almacenar conjuntos de estados posibles en lugar de estados individuales en los diccionarios de transición y usar el módulo random para elegir el siguiente estado del conjunto de estados posibles.

Bueno, aquí les presento una solución recursiva para NFA.

considere la siguiente nfa:

introduzca la descripción de la imagen aquí

Las transiciones se pueden representar utilizando la lista de listas de la siguiente manera:

transición = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]

Nota: El estado 4 es un estado hipotético. Una vez que vas a ese estado, no puedes moverte más. Es útil cuando no puede leer la entrada del estado actual. Usted va directamente al estado 4 y dice que la entrada no se acepta para el progreso actual (verifique otras posibilidades volviendo). por ejemplo, si se encuentra en q1 , y el símbolo de entrada actual es 'a' , pasa al estado 4 y deja de seguir computando.

Aquí está el código de Python:

 #nfa simulation for (a|b)*abb #state 4 is a trap state import sys def main(): transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]] input = raw_input("enter the string: ") input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity if input[index]=='a': input[index]='0' else: input[index]='1' final = "3" #set of final states = {3} start = 0 i=0 #counter to remember the number of symbols read trans(transition, input, final, start, i) print "rejected" def trans(transition, input, final, state, i): for j in range (len(input)): for each in transition[state][int(input[j])]: #check for each possibility if each < 4: #move further only if you are at non-hypothetical state state = each if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states print "accepted" sys.exit() trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:] i = i+1 #increment the counter main() 

salida de muestra: (se aceptan cadenas que terminan con abb)

 enter the string: abb accepted enter the string: aaaabbbb rejected 

......

No necesita un bucle for de rango (len (entrada)) si está usando recursividad. Estás sobre complicando el código. Aquí hay una versión simplificada.

 import sys def main(): transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]] input = raw_input("enter the string: ") input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity if input[index]=='a': input[index]='0' else: input[index]='1' final = "3" #set of final states = {3} start = 0 trans(transition, input, final, start) print "rejected" def trans(transition, input, final, state): for each in transition[state][int(input[0])]: #check for each possibility if each < 4: #move further only if you are at non-hypothetical state state = each if len(input)==1: if (str(state) in final): #last symbol is read and current state lies in the set of final states print "accepted" sys.exit() else: continue trans(transition, input[1:], final, state) #input string for next transition is input[i+1:] main() 

Aquí está mi versión de una implementación dfa si está buscando una más orientada a objetos. Sin embargo, me sorprendió un poco la respuesta de John Coleman.

 class Node: def __init__(self, val): self.val = val self.links = [] def add_link(self, link): self.links.append(link) def __str__(self): node = "(%s):\n" % self.val for link in self.links: node += "\t" + link + "\n" return node def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) def equals(self, node): ok = (self.val == node.val) if len(self.links) == len(node.links): for i in range(len(self.links)): ok = ok and (self.links[i] == node.links[i]) return ok else: return False class Link: def __init__(self, from_node, etiquette, to_node): self.from_node = from_node self.etiquette = etiquette self.to_node = to_node def __str__(self): return "(%s --%s--> %s)" % (self.from_node.val, self.etiquette, self.to_node.val) def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) def equals(self, link): return (self.from_node == link.from_node) and (self.etiquette == link.etiquette) and (self.to_node == link.to_node) class Automata: def __init__(self, initial_node, nodes, terminal_node): self.initial_node = initial_node self.nodes = nodes self.terminal_node = terminal_node def get_next_node(self, current_node, etiquette): for link in current_node.links: if link.etiquette == etiquette: return link.to_node return None def accepts(self, string): node = self.initial_node for character in string: node = self.get_next_node(node, character) return self.terminal_node.equals(node) def __str__(self): automata = "Initial node: %s\nTerminal node: %s\n" % (self.initial_node.val, self.terminal_node.val) for node in self.nodes: automata += node return automata def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) if __name__ == '__main__': pass s0 = Node("s0") s1 = Node("s1") s2 = Node("s2") s0_0_s0 = Link(s0, '0', s0) s0_1_s1 = Link(s0, '1', s1) s1_0_s2 = Link(s1, '0', s2) s1_1_s0 = Link(s1, '1', s0) s2_0_s1 = Link(s2, '0', s1) s2_1_s2 = Link(s2, '1', s2) s0.add_link(s0_0_s0) s0.add_link(s0_1_s1) s1.add_link(s1_0_s2) s1.add_link(s1_1_s0) s2.add_link(s2_0_s1) s2.add_link(s2_1_s2) a = Automata(s0, [s0, s1, s2], s0) print(a) print(a.accepts('1011101')) #True print(a.accepts('10111011')) #False