ADA 3 3 - Programa conversor AFN - AFD

Vista previa del material en texto

Instituto Tecnológico Superior Progreso
 
	
 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
Alumnos:
Madera Poot Wilberth Rafael
Vivas Cetz Juan Alejandro
Couho Pérez Kevin Antonio
Flores Montero Geovanny Alessandro
De la cruz Centeno Miguel Ángel
SEMESTRE:6
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
# 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
 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'],
 ('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 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.
2