hopcroft.py

#!/usr/bin/env python3
"""
    Trabalhos de Formais e Automatos - 2017.2
    Denilson das Mercês Amorim

    O código a seguir transforma um dado DFA em um DFA minímo pelo
    algoritmo de Hopcroft.

    O algoritmo funciona da seguinte maneira:

    Precisamos achar um conjunto de subconjuntos onde cada elemento é um estado,
    tal que esses subconjuntos sejam os maiores possiveis (i.e. cada subconjunto 
    contem absolutamente todos os estados que são equivalentes).

    Para isso, começamos com um conjunto pouco filtrado, de subconjuntos que
    já sabemos que não são equivalentes. Isto é, uma partição de estados finais
    e não-finais.

    A cada iteração do nosso algoritmo, filtramos cada subconjunto nessa partição.
    Sempre que acharmos dois ou mais estados que não são equivalentes em um subconjunto
    em transições por um determinado simbolo c, separamos esse subconjunto em dois, os
    consistentes em c, e os não consistentes em c (mesmo que os não consistentes não
    sejam equivalentes, outras iterações irão lidar com isso).

    Ao fim disso, temos uma partição de estados equivalentes e podemos construir um
    DFA minimo baseado nessa partição. Como último passo, removemos os estados não
    alcançaveis.
"""
from collections import defaultdict


class NFA:
    """
        Essa estrutura representa um automato finito não-deterministico.
        Claramente, podemos também representar um DFA.
    """
    def __init__(self, states, symbols, transition, initial, finals):
        self.states = states
        self.symbols = symbols
        self.transition = transition
        self.initial = initial
        self.finals = finals
        assert isinstance(self.states, set)
        assert isinstance(self.transition, dict)
        assert all((isinstance(v, set) or isinstance(v, frozenset)) 
                for v in self.transition.values())
        assert isinstance(self.finals, set)
        assert self.finals.issubset(self.states)
        assert self.initial in self.states

    def intergize(self):
        """Transforma esse NFA com estados de tipo arbitrário em um NFA
        com estados de tipo inteiro."""
        state2int = {s: i for i, s in enumerate(self.states)}

        initial = state2int[self.initial]
        finals = set(state2int[f] for f in self.finals)
        states = set(state2int[s] for s in self.states)

        trans = defaultdict(set)
        for k, v in self.transition.items():
            q0, s = k
            for q1 in v:
                trans[(state2int[q0], s)].add(state2int[q1])

        trans = dict(trans)
        return NFA(states, self.symbols, trans, initial, finals)
    
    def delta_one(self, q, s):
        """Assumindo que isso é um DFA, retorna um estado ao qual
        iremos quando aplicamos a transição de `q` lendo `s`.

        Caso não haja tal transição, `None` é retornado."""
        try:
            v = self.transition[(q, s)]
        except KeyError:
            return None
        else:
            assert len(v) == 1
            return next(iter(v))

    def is_dfa(nfa):
        """Checa se esse NFA é também um DFA."""
        return all(len(v) <= 1 for v in nfa.transition.values())


def input_dfa():
    """Retorna um DFA lido da entrada do usuário."""
    num_states = int(input())
    states = set(i for i in range(num_states))

    num_symbols = int(input())
    symbols = set(i for i in range(num_symbols))

    initial = int(input())

    num_finals = int(input())
    finals = set([int(f) for f in input().split(',')])

    num_trans = int(input())
    trans = {}
    for i in range(num_trans):
        q0, s, q1 = map(int, input().split(','))
        trans[(q0, s)] = {q1}

    return NFA(states, symbols, trans, initial, finals)

def print_dfa(dfa):
    """Printa o DFA especificado no stream de saída."""
    print(len(dfa.states))
    print(len(dfa.symbols))
    print(dfa.initial)

    print(len(dfa.finals))
    print(','.join([str(f) for f in dfa.finals]))

    total_trans = sum(len(v) for v in dfa.transition.values())
    print(total_trans)
    for k, v in dfa.transition.items():
        q0, c = k
        for q1 in v:
            print(','.join([str(q0), str(c), str(q1)]))


def make_ps_for_q(dfa, partition):
    """Retorna uma hash table onde ao indexar um estado do `dfa`,
    obtem-se o elemento da partição `partition` onde esse estado
    está contido, ou seja o subconjunto de estados provavelmente-equivalentes."""
    find_ps_for_q = dict()
    for ps in partition:
        for q in ps:
            find_ps_for_q[q] = ps
    return find_ps_for_q

def split(dfa, ps, partition):
    """Separa o subconjunto `ps` em dois subconjuntos, um contendo
    estados consitentes em um símbolo c, e os outros não consistentes.

    Se todos os estados em `ps` são equivalentes, retorna uma partição
    contendo somente `ps`."""

    ps_for_q = make_ps_for_q(dfa, partition)
    ps_for_q[None] = set() # para arestas (q, c) inexistentes.

    for c in dfa.symbols:
        good_set = set()
        good_ps = None
        for p in ps:
            this_ps = ps_for_q[dfa.delta_one(p, c)] 
            if good_ps is None:
                good_ps = this_ps
                good_set.add(p)
            elif good_ps == this_ps:
                good_set.add(p)
        if len(good_set) != len(ps):
            good_set = frozenset(good_set)
            return frozenset({good_set, ps - good_set})

    return frozenset({ps})

def hopcroft(dfa):
    """Retorna um DFA mínimio equivalente a `dfa`."""
    partition = {frozenset(dfa.finals), frozenset(dfa.states - dfa.finals)}
    prev_partition = set()

    # Repete até não conseguir mais filtrar a partição.
    while partition != prev_partition:
        prev_partition = partition
        partition = set()
        for ps in prev_partition:
            partition.update(split(dfa, ps, prev_partition))

    ps_for_q = make_ps_for_q(dfa, partition)

    # Constroi o DFA baseado em partition.
    initial = next(ps for ps in partition if dfa.initial in ps)
    finals = {ps for ps in partition if not ps.isdisjoint(dfa.finals)}
    trans = dict()
    for k, v in dfa.transition.items():
        q0, c = k
        assert len(v) == 1
        q1 = next(iter(v))
        trans[(ps_for_q[q0], c)] = {ps_for_q[q1]}

    return NFA(partition, dfa.symbols, trans, initial, finals).intergize()

def reachable(dfa):
    """Retorna um DFA somente com estados alcançaveis."""

    # O estado inicial continua sendo o mesmo.
    initial = dfa.initial

    # Vamos descobrir o conjunto de estados alcançaveis a seguir.
    states = set([initial])
    queue = [initial]
    while len(queue) != 0:
        q = queue.pop()
        for c in dfa.symbols:
            for qnext in dfa.transition[(q, c)]:
                if qnext not in states:
                    states.add(qnext)
                    queue.append(qnext)

    # O conjunto de estados finais é a interseção dos estados alcançaveis
    # com os estados finais do DFA original.
    finals = dfa.finals.intersection(states)

    # Vamos filtrar a tabela de transição para conter apenas os estados alcançaveis.
    trans = {k: v for k, v in dfa.transition.items() if k[0] in states}

    return NFA(states, dfa.symbols, trans, initial, finals).intergize()


def main():
    dfa = input_dfa()
    minimal_dfa = reachable(hopcroft(dfa))
    print_dfa(minimal_dfa)


if __name__ == '__main__':
    main()