NFA Subset Construction

subset.py

nfa = {
        0: {
            'a': { 6 },
            'b': set(),
            'e': { 1 },
        },
        1: {
            'a': { 7 },
            'b': { 4 },
            'e': { 3 },
        },
        2: {
            'a': { 4,6 },
            'b': { 5 },
            'e': set(),
        },
        3: {
            'a': { 5,6 },
            'b': { 2 },
            'e': set(),
        },
        4: {
            'a': { 2,7 },
            'b': set(),
            'e': { 3 },
        },
        5: {
            'a': set(),
            'b': { 0 },
            'e': { 2 },
        },
        6: {
            'a': set(),
            'b': { 3 },
            'e': { 2 },
        },
        7: {
            'a': { 4 },
            'b': set(),
            'e': { 0 },
        },
}

print('NFA')
print(nfa)
print()
print('-------------')
print()

def move(nfa, states, x):
    result = set()
    for state in states:
        for to_state in nfa[state][x]:
            result.add(to_state)
    return frozenset(result)

def eps(nfa, states):
    states = frozenset(states)
    result = frozenset.union(
            states,
            move(nfa, states, 'e')
    )

    if len(result) == len(states):
        return result

    return eps(nfa, result)

def get_dfa(nfa):
    dfa = []

    A = eps(nfa, { 0 })
    print('A', A)
    dfa.append(A)

    i = 0
    while i < len(dfa):
        for x in ('a', 'b'):
            new_state = eps(nfa, move(nfa, dfa[i], x))

            if new_state not in dfa:
                print(
                    chr(ord('A') + len(dfa)),
                    new_state
                )
                dfa.append(new_state)

            to_i = dfa.index(new_state)
            print(
                    chr(ord('A')+i),
                    f'({x})',
                    '->',
                    chr(ord('A')+to_i),
            )
        i += 1

    return dfa


result_dfa = get_dfa(nfa)
states_num = len(result_dfa)

for i, dfa_state in enumerate(result_dfa):
    print(chr(
            ord('A') + i
    ), dfa_state)