Implementación del Algoritmo de Thompson para Automatas Finitos
Publicado por Diego Arevalo (1 intervención) el 05/10/2024 08:55:57
Hola, estoy tratando de crear este algotimo para que procese cadenas, a partir de un automata.
pero siempre recibo este error, al intentar concatenar, unir, etc., no crea lo correspondiente al segundo simbolo.
Procesando símbolo: a
AFN creado para símbolo: a
Procesando símbolo: |
Traceback (most recent call last):
File "c:\Users\diego\Escritorio\Proyecto - Automatas\in.py", line 120, in <module>
afn = construir_afn(expresion_regular) # Ahora almacenamos el autómata generado
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "c:\Users\diego\Escritorio\Proyecto - Automatas\in.py", line 69, in construir_afn
raise ValueError("No hay suficientes AFNs en la pila para aplicar unión.")
ValueError: No hay suficientes AFNs en la pila para aplicar unión.
pueden darme ideas?
pero siempre recibo este error, al intentar concatenar, unir, etc., no crea lo correspondiente al segundo simbolo.
Procesando símbolo: a
AFN creado para símbolo: a
Procesando símbolo: |
Traceback (most recent call last):
File "c:\Users\diego\Escritorio\Proyecto - Automatas\in.py", line 120, in <module>
afn = construir_afn(expresion_regular) # Ahora almacenamos el autómata generado
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "c:\Users\diego\Escritorio\Proyecto - Automatas\in.py", line 69, in construir_afn
raise ValueError("No hay suficientes AFNs en la pila para aplicar unión.")
ValueError: No hay suficientes AFNs en la pila para aplicar unión.
pueden darme ideas?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# Solicitar entradas al usuario"""alfabeto = input("Ingrese el alfabeto (separado por comas, por ejemplo: a,b,c): ").split(',')
expresion_regular = input("Ingrese la expresión regular: ")
cadena = input("Ingrese la cadena a validar: ")"""
# Para las pruebasalfabeto = ['a', 'b']
expresion_regular = 'a|b'
cadena = 'ab'
# *************SE CREAN LAS CLASES********************class Estado:def __init__(self):
self.transiciones = {} # Transiciones a otros estados
self.aceptacion = False # Es un estado de aceptación
class AFN:def __init__(self):
self.inicial = Estado() # Estado inicial
self.aceptacion = Estado() # Estado de aceptación
self.inicial.transiciones = {None: [self.aceptacion]} # Epsilon-transición
# **************SE DEFINEN EL COMPORTAMIENTO DE TRANSICIONES*******************def unir(afn1, afn2):
nuevo_afn = AFN()
nuevo_afn.inicial.transiciones[None] = [afn1.inicial, afn2.inicial]
afn1.aceptacion.aceptacion = False
afn2.aceptacion.aceptacion = False
afn1.aceptacion.transiciones[None] = [nuevo_afn.aceptacion]
afn2.aceptacion.transiciones[None] = [nuevo_afn.aceptacion]
nuevo_afn.aceptacion.aceptacion = True # El nuevo AFN debe tener un estado de aceptación
return nuevo_afn
def concatenar(afn1, afn2):
afn1.aceptacion.transiciones[None] = [afn2.inicial]
afn1.aceptacion.aceptacion = False
return afn1
def cerradura_kleene(afn):
nuevo_afn = AFN()
nuevo_afn.inicial.transiciones[None] = [afn.inicial, nuevo_afn.aceptacion]
afn.aceptacion.transiciones[None] = [afn.inicial, nuevo_afn.aceptacion]
afn.aceptacion.aceptacion = False
nuevo_afn.aceptacion.aceptacion = True # El nuevo estado debe ser aceptable
return nuevo_afn
def cerradura_positiva(afn):
nuevo_afn = AFN()
nuevo_afn.inicial.transiciones[None] = [afn.inicial]
afn.aceptacion.transiciones[None] = [afn.inicial]
afn.aceptacion.aceptacion = False
nuevo_afn.aceptacion.aceptacion = True # El nuevo AFN debe tener un estado de aceptación
return nuevo_afn
# **************FUNCION PARA DEFINIR EL AUTOMATA*******************def construir_afn(expresion):
stack = []
for simbolo in expresion:print(f"Procesando símbolo: {simbolo}") # Imprimir el símbolo actual
if simbolo.isalpha(): # los símbolos son letras
afn = AFN()
estado_intermedio = Estado()
afn.inicial.transiciones[simbolo] = [estado_intermedio]
estado_intermedio.transiciones[None] = [afn.aceptacion]
afn.aceptacion.aceptacion = True
stack.append(afn)
print("AFN creado para símbolo:", simbolo) # Confirmación de creación de AFN
elif simbolo == '|': # Unión
if len(stack) < 2:
raise ValueError("No hay suficientes AFNs en la pila para aplicar unión.")
afn2 = stack.pop()
afn1 = stack.pop()
stack.append(unir(afn1, afn2))
print("AFN unido") # Confirmación de unión
elif simbolo == '.': # Concatenación
if len(stack) < 2:
raise ValueError("No hay suficientes AFNs en la pila para aplicar concatenación.")
afn2 = stack.pop()
afn1 = stack.pop()
stack.append(concatenar(afn1, afn2))
print("AFN concatenado") # Confirmación de concatenación
elif simbolo == '*': # Cerradura de Kleene
if not stack:raise ValueError("No hay AFN en la pila para aplicar la cerradura de Kleene.")
afn = stack.pop()
stack.append(cerradura_kleene(afn))
print("Cerradura de Kleene aplicada") # Confirmación de cerradura
elif simbolo == '+': # Cerradura positiva
if not stack:raise ValueError("No hay AFN en la pila para aplicar la cerradura positiva.")
afn = stack.pop()
stack.append(cerradura_positiva(afn))
print("Cerradura positiva aplicada") # Confirmación de cerradura positiva
if len(stack) != 1:
raise ValueError("La expresión regular no produjo un AFN válido.")
print("AFN final construido") # Confirmación de construcción del AFN
return stack.pop()
# **************FUNCION PARA VALIDAR LA CADENA*******************def validar_cadena(afn, cadena):
estados_actuales = [afn.inicial] # Iniciamos con el estado inicial del AFN
for simbolo in cadena: # Iteramos sobre cada símbolo de la cadena
nuevos_estados = [] # Lista para almacenar nuevos estados alcanzables
for estado in estados_actuales: # Para cada estado actual
if simbolo in estado.transiciones: # Transición para el símbolo actual
nuevos_estados.extend(estado.transiciones[simbolo]) # Agregamos los nuevos estados alcanzables
if None in estado.transiciones: # Si hay una transición epsilon
nuevos_estados.extend(estado.transiciones[None]) # Agregamos los estados alcanzables por epsilon
estados_actuales = nuevos_estados # Actualizamos los estados actuales
for estado in estados_actuales: # Verificamos si alguno de los estados finales es un estado de aceptación
if estado.aceptacion: # Si hay un estado de aceptación
return True # La cadena es aceptada return False # Si no hay estado de aceptación, la cadena no es aceptada# ***********LLAMADA A LA FUNCION PARA DEFINIR EL AUTOMATA**********************afn = construir_afn(expresion_regular) # Almacenamos el autómata generado
# ***********LLAMADA A LA FUNCION VALIDAR LA CADENA**********************es_valida = validar_cadena(afn, cadena)
print(f"La cadena {'es válida' if es_valida else 'no es válida'} para la expresión regular.")
Valora esta pregunta
0