DFA, NFA and Epsilon-NFA implementations

automata_utils.py

EPS = "eps"
ERROR = "Error"


def get_file_data(filename: str):
    with open(filename, "r") as file:
        data = file.read()
    return data.splitlines()

dfa.py

from automata_utils import ERROR


def accepts(delta: dict, word: str, initial: str, final: set):
    for c in word:
        initial = delta.get((initial, c), ERROR)
        if initial == ERROR:
            return False
    return initial in final

e_nfa.py

from automata_utils import EPS
from automata_utils import ERROR


def epsilon_closure(delta: dict, states: set):
    unchecked_stack = list(states)
    closure = set(states)

    while unchecked_stack:
        state = unchecked_stack.pop()
        next_states = delta.get((state, EPS), ERROR)

        if next_states != ERROR:
            for next_state in next_states:
                if next_state not in closure:
                    closure.update(next_state)
                    unchecked_stack.append(next_state)
    return closure


def accepts(delta: dict, word: str, initial: set, final: set):
    initial = epsilon_closure(delta, initial)

    result = False
    for c in word:
        next_states = set()
        for cur_state in initial:
            next_states_t = delta.get((cur_state, c), ERROR)
            if next_states_t != ERROR:
                next_states.update(next_states_t)

            next_states_e = delta.get((cur_state, EPS), ERROR)
            if next_states_e != ERROR:
                result |= accepts(delta, word, next_states_e, final)
        if not next_states:
            return False

        initial = next_states
    result |= len(set.intersection(initial, final)) > 0
    return result

nfa.py

from automata_utils import ERROR


def accepts(delta: dict, word: str, initial: set, final: set):
    for c in word:
        next_states = set()

        for cur_state in initial:
            next_states_t = delta.get((cur_state, c), ERROR)

            if next_states_t != ERROR:
                next_states.update(next_states_t)

        if not next_states:
            return False

        initial = next_states
    return len(set.intersection(initial, final)) > 0


def contains(delta: dict, word: str, initial: set, final: set):
    """
        if found returns index of last substring char, else returns -1
    """
    for i, c in enumerate(word):
        next_states = set()
        for cur_state in initial:
            next_states_t = delta.get((cur_state, c), ERROR)

            if next_states_t != ERROR:
                next_states.update(next_states_t)

        if not next_states:
            return -1
        elif set.intersection(next_states, final):
            return i

        initial = next_states
    return -1