0

Estoy programando un automata con transiciones de (estado,simbolo,estado) estados, estado inicial, estados finales, alfabeto, transiciones y la palabra a leer estan guardadas por `

dic = {
"estados": input().split(),
"alf":input().split(),
"q0": input(),
"qF": input().split(),
"transiciones": input().split(),
"palabra":input(),}

Y para leer las transiciones y hacerlas las tengo como:

def trn():
estado_actual = dic["q0"]
for n in dic["transiciones"]:
    for x in dic["palabra"]:
        dic["transiciones"] = n.strip("()").split(",")
        if estado_actual == dic["transiciones"][0]:
            if x == dic["transiciones"][1]:
                estado_actual = dic["transiciones"][2]
                print(dic["palabra"],estado_actual)
            elif dic["transiciones"][1] == "#":
                estado_actual = dic["transiciones"][2]
                print(dic["palabra"],estado_actual)
if estado_actual in dic["qF"]:
    print("Aceptada")
else:
    print('Rechazada')`

El problema es que palabras invalidas siguen el bucle hasta aceptarlas

introducir la descripción de la imagen aquí

Aqui por ejemplo los estados son A B C, simbolos son 0 1, estado inicial A, Final C, las transiciones son (A,0,A) (A,1,B) (B,1,C) y la palabra a leer es 0001, con esta palabra el estado final deberia ser de B y la palabra deberia ser rechazada pero sigue hasta llegar a C y por eso queda aceptada.

Probe con poner un len(dic["palabra"]) para que no siga pero me invalida ahi la cadena entonces no se que hacer

3
  • Con esta línea dic["transiciones"] = n.strip("()").split(",") destruyes el contenido inicial de la entrada. La reemplazas con ['A', '0', 'A'].
    – Candid Moe
    el 11 may. 2022 a las 20:38
  • Entiendo que reemplazo el contenido inicial pero necesito el strip y el split para poder leer las transiciones
    – lol lmao
    el 11 may. 2022 a las 20:50
  • Mejor preparar el diccionario antes de entrar a procesar.
    – Candid Moe
    el 11 may. 2022 a las 20:59

1 respuesta 1

0

Problemas

En la línea

dic["transiciones"] = n.strip("()").split(",")

estas reemplazado la lista de transiciones:

['(A,0,A)', '(A,1,B)', '(B,1,C)']

con

['A', '0', 'A']

lo que genera caos.

Hay otras cosas que tampoco están claras en tu algoritmo, pero no creo que valga la pena discutirlas

Una solución más simple es esta:

def trn(estado_inicial, estado_final, palabra):
    #   Revisar si llegamos al destino al acabarse la palabra
    if not palabra:
        return estado_inicial == estado_final

    #   Buscar en las transiciones una que calce con este estado+letra
    #   alternativas es una lista de transiciones validas en este estado y letra
    alternativas = [trans for trans in dic["transiciones"] if trans[0] == estado_inicial and trans[1] == palabra[0]]
    #   Recorrer la lista de alternativas y ver si alguna lleva a destino
    for alt in alternativas:
        if trn(alt[2], estado_final, palabra[1:]):
            return True
    #   Ninguna alternativa lleva a destino
    return False

Esta función recursiva chequea si es posible ir del estado inicial al estado final usando la palabra (completa).

La función primero chequea la condición de término: si la palabra está vacía, sólo queda revisar si el estado inicial es el estado final deseado. Retornar True en caso de éxito.

Si todavía queda palabra, extraer la primera letra y luego recorrer las transiciones seleccionando las que comiencen en el estado actual y acepten la letra en cuestión.

Si la lista está vacia, por aquí no hay solución.

Si la lista tiene elementos, probar cada uno para ver si alguno lleva a la solución. Para esto se invoca la función recursivamente pasando como estado inicial el estado destino que nos da la transición, y pasando la palabra recortada en su primera posición.

Demo

dic = {
"estados": ["A", "B", "C"],
"alf": ["0", "1"],
"q0": "A",
"qF": "C",
"transiciones": [["A","0","A"], ["A","1","B"], ["B","1","C"]],
"palabra": "0001"}

def trn(estado_inicial, estado_final, palabra):
    #   Revisar si llegamos al destino al acabarse la palabra
    if not palabra:
        return estado_inicial == estado_final

    #   Buscar en las transiciones una que calce con este estado+letra
    #   alternativas es una lista de transiciones validas en este estado y letra
    alternativas = [trans for trans in dic["transiciones"] if trans[0] == estado_inicial and trans[1] == palabra[0]]
    #   Recorrer la lista de alternativas y ver si alguna lleva a destino
    for alt in alternativas:
        if trn(alt[2], estado_final, palabra[1:]):
            return True
    #   Ninguna alternativa lleva a destino
    return False


tests = [
    "011",
    "0001",
    "00011"
]

for test in tests:
    print(test, end=" ")
    if trn("A", "C", test):
        print("Aceptada")
    else:
        print('Rechazada')

produce:

011 Aceptada
0001 Rechazada
00011 Aceptada

Process finished with exit code 0
4
  • Agradezco tu ayuda pero desgraciadamente deben ser por consola todos los datos, por eso usaba el ' dic["transiciones"] = n.strip("()").split(",")' para limpiar los () y separar las comas,
    – lol lmao
    el 11 may. 2022 a las 22:29
  • @lollmao Siempre puedes cambiar la parte de pedir los datos ...
    – Candid Moe
    el 11 may. 2022 a las 22:37
  • Lo comprendo pero sin el strip y el split los datos no me quedan separados en estado,simbolo,estado
    – lol lmao
    el 11 may. 2022 a las 22:46
  • @lollmao. Tienes que preparar los datos antes de llamar a la función. Dividir para reinar.
    – Candid Moe
    el 11 may. 2022 a las 22:56

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.