Matching a string against an NFA in Python

nfa.py

ε = object()

# NFA for a*ab;
#
#       ε      a      b
# ->(0)--->(1)--->(2)--->((3))
#    ^ \
#    |__|
#      a
#
# Derived from the concatenation of a*:
#
# ->((0))\
#     ^   |
#     |___|
#       a
#
# And ab:
#
#       a      b
# ->(0)--->(1)--->((2))
#
accepting_states = {3}
transition = {
    0: {"a": {0}, ε: {1},},
    1: {"a": {2},},
    2: {"b": {3},},
    3: {},
}


def δ(s, c):
    return frozenset(transition[s].get(c, set()))


def ε_closure(states):
    states = states.copy()
    to_visit = list(states)
    for st in to_visit:
        equiv = transition[st].get(ε, set())
        states |= equiv
        to_visit.extend(equiv)
    return frozenset(states)


matching_string = "aabk"

print("NFA match")
configuration = {(matching_string, st) for st in ε_closure({0})}
accepted = False

while configuration and not accepted:
    new_configuration = set()
    for input_string, state in configuration:
        possible_transitions = transition[state]
        if input_string:
            char = input_string[0]
            if char in possible_transitions:
                new_configuration |= {
                    (input_string[1:], dest)
                    for dest in ε_closure(possible_transitions[char])
                }
        elif state in accepting_states:
            accepted = True
            break
    configuration = new_configuration

print("Accepted" if accepted else "Not accepted")


def Ε():
    seen = set()
    for transitions in transition.values():
        for c in transitions:
            if c is not ε and c not in seen:
                yield c
                seen.add(c)


def Delta(q, c):
    return frozenset().union(*(δ(s, c) for s in q))


# Subset construction
q0 = ε_closure({0})
Q = {q0}
WorkList = {q0}
T = {}

while WorkList:
    q = WorkList.pop()
    for c in Ε():
        t = ε_closure(Delta(q, c))
        if t:
            T.setdefault(q, {})[c] = t
            if t not in Q:
                Q.add(t)
                WorkList.add(t)


# Build DFA
D_start_state = None
D_accepting_states = set()
D_state_numbers = dict((q, i) for i, q in enumerate(Q))
D = {}

for q in Q:
    state = D_state_numbers[q]
    if q == q0:
        D_start_state = state
    if q & accepting_states:
        D_accepting_states.add(state)
    D[state] = {k: D_state_numbers[v] for k, v in T.get(q, {}).items()}


print("DFA match")
state = D_start_state
for c in matching_string:
    possible_transitions = D[state]
    if c not in possible_transitions:
        print("Not accepted")
        break
    state = possible_transitions[c]
else:
    if state in D_accepting_states:
        print("Accepted")
    else:
        print("Not accepted")