Funkcje programu · Równoważność osiągalnych stanów DFA

def dfa_classes(table, accepting):
    if type(table) is not list or not 1 <= len(table) <= 16:
        raise ValueError("state count")
    n = len(table)
    if type(table[0]) is not list or not 1 <= len(table[0]) <= 4:
        raise ValueError("alphabet size")
    width = len(table[0])
    if any(type(row) is not list or len(row) != width or
           any(type(x) is not int or not 0 <= x < n for x in row)
           for row in table):
        raise ValueError("complete transition table")
    if type(accepting) is not set or any(
        type(x) is not int or not 0 <= x < n for x in accepting):
        raise ValueError("accepting states")
    seen, pending = {0}, [0]
    while pending:
        for dest in table[pending.pop()]:
            if dest not in seen:
                seen.add(dest); pending.append(dest)
    groups = [g for g in (seen & accepting, seen - accepting) if g]
    while True:
        owner = {s: i for i, g in enumerate(groups) for s in g}
        refined = []
        for group in groups:
            buckets = {}
            for state in sorted(group):
                key = tuple(owner[d] for d in table[state])
                buckets.setdefault(key, set()).add(state)
            refined.extend(buckets.values())
        if len(refined) == len(groups):
            return sorted([sorted(g) for g in refined])
        groups = refined