brzozowski.py

#!/usr/bin/env python3
"""
    Trabalho de Linguagens Fôrmais e Automatos - 2017.2
    Denilson das Mercês Amorim

    O código a seguir transforma um DFA arbitrário em seu minímo equivalente
    através do algoritmo de Brzozowski.
    
    Mesmo que a especificação do trabalho peça o uso do algoritmo de Hopcroft,
    resolvi programar este algoritmo por dois motivos:

        1) Ele é extremamente elegante e interessante. Queria vê-lo em ação.
        2) Exercitar meus conhecimentos em automata, visto que é preciso implementar
           a construção de Rabin-Scott e um reversor de automatos como parte do
           algoritmo.

    Ainda assim, uma versão usando o algoritmo de Hopcroft será implementada
    e submetida juntamente a essa implementação.

    O algoritmo de Brzozowski funciona baseado na observação de que dado um NFA
    com vários estados iniciais (através de um verdadeiro inicial de transições vazias),
    todos os caminhos que aceitam uma mesma palavra como prefixo irão se tornar
    um único estado ao transformar o NFA em DFA com a construção por subconjuntos.

    Dessa forma, se temos um DFA chamado A, e achamos o seu reverso NFA reverso B,
    e então o convertemos para um DFA C, eliminamos todos os caminhos com sufixo
    duplicado. Para finalizar, revertemos novamente o automato C, e o transformamos
    em um DFA, removendo assim todos os caminhos com prefixo repetido. Feito isso,
    temos um DFA mínimo equivalente a A.
"""
from collections import defaultdict

# Símbolo de transição vazia.
LAMBDA = object()


class NFA:
    """
        Essa estrutura representa um automato finito não-deterministico.
        Claramente, podemos também representar um DFA com essa estrutura.
    """
    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 lambda_closure(self, from_states):
        """Retorna um conjunto contendo todos os estados
        que se pode chegar tomando transições vazias
        a partir de cada um dos estados em `from_states`.
        
        O conjunto retornado sempre contem, no mínimo,
        os próprios `from_states`."""
        closure = set(q for q in from_states)
        queue = list(closure)
        while len(queue) > 0:
            q = queue.pop()
            for r in self.transition.get((q, LAMBDA), []):
                if r not in closure:
                    closure.add(r)
                    queue.append(r)
        return closure

    def delta(self, qs, c):
        """Retorna o conjunto de todos os estados alcançaveis
        partindo de qualquer um dos estados `qs` lendo `c`, não
        incluindo transições vazias."""
        resp = set()
        for q in qs:
            resp.update(self.transition.get((q, c), []))
        return resp

    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 reverse(nfa):
    """Retorna o NFA reverso do NFA especificado."""
    # Criamos um novo estado inicial.
    initial = object()

    # Tornamos o antigo estado inicial o novo estado final.
    finals = {nfa.initial}

    # Os estados são os mesmos com a adição do novo inicial.
    states = {initial} | nfa.states

    # Invertemos todas as arestas.
    trans = defaultdict(set)
    for k, v in nfa.transition.items():
        q0, s = k
        for q1 in v:
            trans[(q1, s)].add(q0)
    
    # Adicionamos uma transição inicial para todos os antigos estados finais.
    trans[(initial, LAMBDA)].update(nfa.finals)

    trans = dict(trans)
    return NFA(states, nfa.symbols, trans, initial, finals).intergize()

def subset(nfa):
    """Retorna um DFA equivalente ao NFA especificado.
    
    Essa função não é de proposito geral! Essa função elimina o estado
    inicial auxiliar produzido pela função reverse. Para mais detalhes,
    ver https://cs.stackexchange.com/a/6152."""

    # O tipo dos nossos estados durante a construção será frozenset,
    # pois todos os estados aqui serão subsets e não dá para ser um set
    # porque este é mutável e portanto não hasheavel.

    # O estado inicial deve ser o feixo do antigo inicial.
    # Nota: Removemos aqui o estado inicial auxiliar! Se retirarmos
    # essa remoção voltamos a ter uma função subset de proposito geral.
    initial = nfa.lambda_closure({nfa.initial}) - {nfa.initial}
    initial = frozenset(initial)

    # Acharemos todos os estados no percorrer do algoritmo, mas já
    # sabemos que o inicial existe.
    states = set([initial])

    # Acharemos as transições também no algoritmo.
    trans = defaultdict(set)

    queue = [initial]
    while len(queue) > 0:
        q = queue.pop()
        for c in nfa.symbols:
            # Acha todos os estados que podemos alcançar do subset q lendo c. 
            qnext = nfa.lambda_closure(nfa.delta(q, c))
            qnext = frozenset(qnext)

            # Adiciona essa transição, do subset q para o subset qnext.
            trans[(q, c)].add(qnext)

            # Se nunca vimos esse subset, ainda precisamos trabalhar nele.
            if qnext not in states:
                states.add(qnext)
                queue.append(qnext)

    # Vamos achar os estados finais. Um subset é final se conter
    # qualquer estado final do NFA original.
    finals = {qs for qs in states if not qs.isdisjoint(nfa.finals)}

    trans = dict(trans)
    return NFA(states, nfa.symbols, trans, initial, finals).intergize()

def main():
    dfa = input_dfa()
    reverse_dfa = subset(reverse(dfa))
    minimal_dfa = subset(reverse(dfa))
    print_dfa(minimal_dfa)


if __name__ == '__main__':
    main()