ADA 3 3 - Programa conversor AFN - AFD

Vista previa del material en texto

Instituto Tecnológico Superior Progreso 
1 
 
 
 
 
 
 
 
 
 
 Instituto Tecnológico Superior Progreso 
CARRERA: 
Ingeniería en Sistemas Computacionales 
 
MATERIA: 
Lenguajes y Autómatas I 
TAREA: 
ADA 3.3 - Programa conversor AFN – AFD 
 
MAESTRO: 
Holzen Atocha Martínez García 
Alumno: 
Madera Poot Wilberth 
Matricula:04200014 
 
SEMESTRE:6 
 
 
 
 
 
 
 
 
 
Instituto Tecnológico Superior Progreso 
2 
 
 
 
 
 
 
 
Codigo: 
# Definición de la clase Autómata Finito No Determinístico (AFN) 
class AFN: 
 def __init__(self, Q, Sigma, delta, q0, F): 
 self.Q = Q # Conjunto de estados 
 self.Sigma = Sigma # Alfabeto de entrada 
 self.delta = delta # Función de transición 
 self.q0 = q0 # Estado inicial 
 self.F = F # Conjunto de estados finales 
Instituto Tecnológico Superior Progreso 
3 
 
 
# Definición de la clase Autómata Finito Determinístico (AFD) 
class AFD: 
 def __init__(self, Q, Sigma, delta, q0, F): 
 self.Q = Q # Conjunto de estados 
 self.Sigma = Sigma # Alfabeto de entrada 
 self.delta = delta # Función de transición 
 self.q0 = q0 # Estado inicial 
 self.F = F # Conjunto de estados finales 
 
# Función para obtener el conjunto de estados alcanzables desde un estado con 
un símbolo de entrada 
def transicion(afn, estados, simbolo): 
 resultado = set() 
 for estado in estados: 
 resultado |= set(afn.delta.get((estado, simbolo), [])) 
 return resultado 
 
# Función para convertir un AFN a un AFD 
def afn_a_afd(afn): 
 q0 = frozenset([afn.q0]) # Estado inicial del AFD 
 Q = set([q0]) # Conjunto de estados del AFD 
 Sigma = afn.Sigma # Alfabeto de entrada del AFD 
 F = set() # Conjunto de estados finales del AFD 
 delta = {} # Función de transición del AFD 
Instituto Tecnológico Superior Progreso 
4 
 
 
 por_procesar = [q0] # Lista de estados que aún no han sido procesados 
 while por_procesar: 
 estado_actual = por_procesar.pop(0) 
 for simbolo in Sigma: 
 nuevo_estado = frozenset(transicion(afn, estado_actual, simbolo)) 
 if nuevo_estado not in Q: 
 Q.add(nuevo_estado) 
 por_procesar.append(nuevo_estado) 
 delta[(estado_actual, simbolo)] = nuevo_estado 
 if afn.F.intersection(nuevo_estado) and nuevo_estado not in F: 
 F.add(nuevo_estado) 
 
 return AFD(Q, Sigma, delta, q0, F) 
 
# Ejemplo de uso 
afn = AFN( 
 Q = {'q0', 'q1', 'q2'}, 
 Sigma = {'0', '1'}, 
 delta = { 
 ('q0', '0'): ['q0', 'q1'], 
 ('q0', '1'): ['q0'], 
 ('q1', '0'): ['q2'], 
 ('q1', '1'): ['q2'], 
 ('q2', '0'): ['q2'], 
Instituto Tecnológico Superior Progreso 
5 
 
 ('q2', '1'): ['q2'] 
 }, 
 q0 = 'q0', 
 F = {'q1'} 
) 
 
afd = afn_a_afd(afn) 
 
print("AFN:") 
print("Q =", afn.Q) 
print("Sigma =", afn.Sigma) 
print("delta =", afn.delta) 
print("q0 =", afn.q0) 
print("F =",) 
Funcionamiento del código: 
Ambas clases tienen los mismos atributos: el conjunto de estados Q, el alfabeto de 
entrada Sigma, la función de transición delta, el estado inicial q0 y el conjunto de 
estados finales F. A continuación, definimos una función de transición (affn, 
estados, símbolo) que acepta como argumentos AFN el conjunto de estados y el 
símbolo del símbolo de entrada. La función devuelve una matriz de estados a los 
que se puede acceder desde cualquier estado leyendo el ID de entrada en el 
estado especificado. Para ello se transporta el estado de cada estado y se obtiene 
el número de estados a los que se puede llegar leyendo el símbolo AFN con la 
función de transición AFN. La transformación se realiza mediante el algoritmo de 
construcción AFN y AFD, que consiste en iniciar el AFN desde un estado inicial 
con un conjunto de estados alcanzables y computar recursivamente los estados 
alcanzables de cada conjunto de estados ya procesados, leyéndolos todos. En 
cada iteración del algoritmo, se construyen nuevos estados del DFA y se agregan 
a la tabla de transición delta. Para implementar el algoritmo de construcción DFA, 
la lista to_process se utiliza para realizar un seguimiento de los estados que aún 
no se han procesado. Luego itera sobre los conjuntos de estados en la lista 
Instituto Tecnológico Superior Progreso 
6 
 
to_process y calcula nuevos estados para cada estado alcanzado cuando se lee 
cada símbolo del alfabeto de entrada usando la función de transición. Si el nuevo 
estado aún no se ha procesado, se agrega a la lista to_process.