nfa_to_dfa.py

from os import sep
from typing import final
import pandas as pd
import numpy as np

df = pd.read_csv("ThompsonInput.csv", na_values="-", index_col=["states"])

print(df)

dfa_state_var = 'A'

dfa_states = dict()


def get_eclosure(S):

    P = list(S)
    C = set(P)


    while len(P) > 0:
        t = P.pop()
        edges = [df.loc[t]["e1"], df.loc[t]["e2"]]
        edges = [int(e) for e in edges if e == e]

        for u in edges:

            if u not in C:
                P.append(u)
                C.add(u)
    return list(C)


def move(states, ip):

    op_states = list()

    for s in states:
        op_states.append(df.loc[s][ip])
    return [int(e) for e in op_states if e == e]


def subset_construction(S1, dfa):

    unmarked = list()
    unmarked.append(S1)
    marked = list()
    while len(unmarked) > 0:
        dfa_state = unmarked.pop()
        marked.append(dfa_state)

        global dfa_state_var
        curr_state = list(dfa_states.keys())[list(
            dfa_states.values()).index(dfa_state)]
        next_state = curr_state

        for ip in ["a", "b"]:
            pass
            S2 = get_eclosure(move(dfa_state, ip))
            if S2 not in unmarked and S2 not in marked:
                unmarked.insert(0, S2)

            if S2 not in dfa_states.values():
                dfa_state_var = chr(ord(dfa_state_var) + 1)
                next_state = dfa_state_var
                dfa_states[next_state] = S2
            else:
                next_state = list(dfa_states.keys())[
                    list(dfa_states.values()).index(S2)]
            dfa[curr_state + " " + ip] = next_state
    return dfa


def print_dfa(dfa, dfa_states):
    print("\nDFA\n\ta\tb\n")
    for state in dfa_states.keys():
        print(state, "\t", dfa[state+" a"], "\t", dfa[state+" b"])


if __name__ == '__main__':

    st = input("Input string to match the Pattern (a|b)*abb :  ")

    final_state = 10
    initial_state = 'A'

    A = get_eclosure([0])

    print("Thompson Construction Table : \n")
    print(df)

    dfa_states[dfa_state_var] = A

    dfa = dict()
    dfa = subset_construction(A, dfa)
    print("\nDFA States : ", dfa_states)
    print_dfa(dfa, dfa_states)

    next_state = initial_state
    print("\nPath on dfa \nA ", end="")
    for i in range(len(st)):
        ch = st[i]
        next_state = dfa[next_state + " " + ch]
        print("--", ch, "--> ", next_state, end=" ", sep="")

    print("\n\nLast state : ", dfa_states[next_state])
    if final_state in dfa_states[next_state]:
        print("Accepted")
    else:
        print("Rejected")