automaton.py

#!/usr/bin/env python3
"""
             a       a
end <---(in)--->[1]<--->[2]--> end
"""
EOF = ''

# aa*
language = [
    {EOF: True, 'a': 1},
    {'a': 2},
    {'a': 1, EOF: True}
]


def match(input: iter, language, state=0):
    node = language[state]
    try:
        state = node[next(input)]
    except StopIteration:
        return node.get(EOF, False)
    except KeyError:
        return False
    return match(input, language, state)


def match_iter(input, language, state=0):
    for c in input:
        try:
            state = language[state][c]
        except KeyError:
            return False
    return language[state].get(EOF, False)