def recognize(fsm, sentence):
    # fsm = (startstate, list-of-finals, list-of-arcs)
    # an arc is a (origin,terminus,symbol)-tuple.
    state = fsm[0]
    for symbol in sentence:
        foundArc = False
        for (origin, terminus, x) in fsm[2]:
            if origin == state and x == symbol:
                # we found an arc for this symbol!
                state = terminus
                foundArc = True
                break
        if not foundArc:
            # we never found an arc for this symbol
            return False
    # we made it all the way to the last symbol
    # but are we in a final state?
    if state in fsm[1]:
        return True
    else:
        return False