99 lines
4.2 KiB
Python
99 lines
4.2 KiB
Python
"""Autómata finito determinista"""
|
|
#Código adaptado del original de Vijaya Gajanan
|
|
#https://medium.com/swlh/automata-theory-in-python-part-1-deterministic-finite-automata-95d7c4a711f5
|
|
|
|
class DFA:
|
|
|
|
def __init__(self):
|
|
#Se inicia el objeto DFA
|
|
self.Q = self.populate_states()
|
|
self.SIGMA = self.populate_alphabet()
|
|
self.DELTA = self.populate_transition_function()
|
|
self.START_STATE, self.ACCEPT_STATES = self.set_start_accept()
|
|
self.CURRENT_STATE = None
|
|
|
|
def set_start_accept(self):
|
|
#Toma el estado inicial (START_SATATE) y los estados de aceptación (ACCEPT_STATE) dado por el usuario y checa si pertenecen al conjunto de estados
|
|
while(True):
|
|
start = input("Da el estado inicial: ")
|
|
accept = input("Da el o los estados de aceptación (separados por espacio): ").split()
|
|
#Se asegura que el estado inicial y de aceptación estén en el conjunto
|
|
if (start in self.Q) and (set(accept).issubset(set(self.Q))):
|
|
return start, accept
|
|
else:
|
|
print("Por favor da estados que estén en tu conjunto de estados Q : {}.\nLos estados de aceptación deben ser un subconjunto de Q\n".format(self.Q))
|
|
|
|
def populate_states(self):
|
|
#Toma los estados dados por el usuario (Q)
|
|
Q_input = input("Da la lista de estados separados por espacio: ").split()
|
|
print("Estados : {}".format(Q_input))
|
|
return Q_input
|
|
|
|
def populate_alphabet(self):
|
|
#Toma el alfabeto dado por el usuario (SIGMA)
|
|
SIGMA_input = input("Da el alfabeto de entrada separado por espacios: ").split()
|
|
print("Alfabeto : {}".format(SIGMA_input))
|
|
return SIGMA_input
|
|
|
|
def populate_transition_function(self):
|
|
#Crea la función de transición (Q X SIGMA -> Q) y la imprime
|
|
transition_dict = {el : {el_2 : 'RECHAZO' for el_2 in self.SIGMA} for el in self.Q}
|
|
|
|
for key, dict_value in transition_dict.items():
|
|
print("Da la transición para el estado {}. De ser necesario, usa 'RECHAZO'.".format(key))
|
|
|
|
for input_alphabet, transition_state in dict_value.items():
|
|
transition_dict[key][input_alphabet] = input("ESTADO ACTUAL : {}\tALFABETO DE ENTRADA : {}\tSIGUIENTE ESTADO : ".format(key, input_alphabet))
|
|
|
|
print("\nFUNCIÓN DE TRANSICIÓN Q X SIGMA -> Q")
|
|
print("ESTADO ACTUAL\tALFABETO DE ENTRADA\tPRÓXIMO ESTADO")
|
|
for key, dict_value in transition_dict.items():
|
|
for input_alphabet, transition_state in dict_value.items():
|
|
print("{}\t\t{}\t\t{}".format(key, input_alphabet, transition_state))
|
|
|
|
return transition_dict
|
|
|
|
def run_state_transition(self, input_symbol):
|
|
#Toma el estado actual y va al siguinete estado de acuerdo al símbolo de entrada
|
|
if (self.CURRENT_STATE == 'RECHAZO'):
|
|
return False
|
|
print("ESTADO ACTUAL : {}\tSÍMBOLO DE ENTRADA : {}\t PRÓXIMO ESTADO : {}".format(self.CURRENT_STATE, input_symbol, self.DELTA[self.CURRENT_STATE][input_symbol]))
|
|
self.CURRENT_STATE = self.DELTA[self.CURRENT_STATE][input_symbol]
|
|
return self.CURRENT_STATE
|
|
|
|
def check_if_accept(self):
|
|
#Checa si el estado actual es de aceptación
|
|
if self.CURRENT_STATE in self.ACCEPT_STATES:
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def run_machine(self, in_string):
|
|
#Corre la máquina con la cadena de entrada
|
|
self.CURRENT_STATE = self.START_STATE
|
|
for ele in in_string:
|
|
check_state = self.run_state_transition(ele)
|
|
#Checa si el estado no es RECHAZO
|
|
if (check_state == 'RECHAZO'):
|
|
return False
|
|
return self.check_if_accept()
|
|
|
|
if __name__ == "__main__":
|
|
check = True
|
|
print("\nAutómata Finito Determinista (DFA).")
|
|
machine = DFA()
|
|
while(check):
|
|
choice = int(input("\nElige la opción:\n1. Correr el DFA con la cadena de entrada\n2. Cambiar el DFA\n3. Salir \nDa Opción : "))
|
|
if (choice == 2):
|
|
machine = DFA()
|
|
elif (choice == 1):
|
|
input_string = list(input("Da la cadena de entrada : "))
|
|
print("ACEPTADA" if machine.run_machine(input_string) else "RECHAZADA")
|
|
else:
|
|
check = False
|
|
|
|
|
|
|
|
|
|
|