walk-fsm.py

#!/usr/bin/env python3

edges = {(1, 'a'): [2, 3],
         (2, 'a'): [2],
         (3, 'b'): [4, 2],
         (4, 'c'): [5]}

edges2 = {(1, 'a'): [1],
          (2, 'a'): [2]}

accepting = [5]
accepting2 = [2]


def find_edge(edges, marker):
    return next((edge, paths) for edge, paths in edges.items()
                if edge[0] == marker)


def nfsmaccepts(current, edges, accepting, visited):
    def walk(current, visited):
        edge, paths = find_edge(edges, current)
        if current in accepting:
            yield ''
        elif any(p in accepting for p in paths):
            yield edge[1]
        else:
            new_paths = [p for p in paths if p not in visited]
            new_visited = visited + [current]
            for path in new_paths:
                found_path = list(walk(path, new_visited))
                if found_path:
                    yield edge[1] + ''.join(found_path)
    paths = list(walk(current, visited))
    return None if not paths else paths[0]


def test_nfsmaccepts():
    test_cases = [[(1, edges, accepting, []), 'abc'],
                  [(1, edges, [4], []), 'ab'],
                  [(1, edges2, accepting2, []), None],
                  [(1, edges2, [1], []), '']]
    for case, test_case in enumerate(test_cases):
        test_input, expected = test_case
        result = nfsmaccepts(*test_input)
        passes = 'SUCCESS' if result == expected else 'FAIL'
        print('Test {case}: {passes} ('
              '"{result}" == "{expected}")'.format(**locals()))


if __name__ == '__main__':
    test_nfsmaccepts()