nfa.py

from collections import defaultdict

class NFA: 

    def __init__(self, q0, qF):
        
        # set start and set of final positions
        self.q0 = q0
        self.qF = set(qF)

        # store transitions in distionary
        self.transitions = defaultdict(lambda: defaultdict(set))


    def addTransition(self, start_q, char, target_q):
        self.transitions[start_q][char].add(target_q)


    def reachable(self, state):

        reachable = set([state])
        todo = [state]

        # check while state in 
        while todo:
            state = todo.pop()

            for other in self.transitions.get(state, {}).get('', []):
                reachable.add(other)
                todo.append(other)

        return reachable

    def simulate(self, state, strng):

        if strng == '':
            return self.reachable(state) & self.qF
        
        for e in self.reachable(state):

            for s in self.transitions.get(e, {}).get(strng[0], []):

                if self._recognize(s, strng[1:]):
                    return True

        return False