Minimização de AFD

Em ciência da computação, mais especificamente no ramo da teoria dos autômatos, Minimização de AFD é o processo de transformação de um dado autômato finito determinístico (AFD) em outro equivalente que tenha um número mínimo de estados. Aqui, dois AFDs são ditos equivalentes se eles descrevem a mesma linguagem regular. Vários algoritmos diferentes que realizam essa tarefa estão descritos em livros-texto padrões que abordam a teoria dos autômatos.

AFD Mínimo

Para cada linguagem regular passível de ser aceita por um AFD, existe um AFD com um número mínimo de estados (e portanto com esforço mínmo de programação para criá-lo e usá-lo), e único (embora possam ser dados nomes diferentes a estados).

Há três classes de estados que podem ser removidos/mesclados ao AFD original sem afetar as linguagens que esse aceita:

• Estados inalcançáveis são aqueles estados impossíveis de se alcançar a partir do estado inicial do AFD, para qualquer cadeia de entrada.
• Estados mortos são quaisquer estados, exceto os de aceitação, cujas transições para todo caracter de entrada tem ele próprio como destino. Eles são também conhecidos como Estados Armadilha (Trap States) pois uma vez alcançados, não há escapatória.
• Estados indistinguíveis são estados indistintos entre si, para qualquer cadeia de entrada.

A minimização do AFD é geralmente feita em três passos, correpondentes às remoções/mesclagens dos estados relevantes. Como a eliminação dos estados indistinguíveis é o mais caro computacionalmente, esse é normalmente o último passo a ser dado.

Estados Inalcançáveis

O estado p do AFD M=(Q, Σ, δ, q₀, F) é inalcançável se não existe qualquer cadeia w em ∑* tal que p=δ(q₀, w). Estados alcançáveis podem ser obtidos pelo seguinte algoritmo:

let estados_alcancaveis:= {q0};
let novos_estados:= {q0};
do {
    temp:= conjunto vazio;
    for each q in novos_estados do
        for all c in ∑ do
            temp:= temp ∪ {p tal que p=δ(q,c)};
        end;
    end;
    novos_estados:= temp \ estados_alcancaveis;
    estados_alcancaveis:= estados_alcancaveis ∪ novos_estados;
} while(novos_estados ≠ conjunto vazio);
estados_inalcancaveis:= Q \ estados_alcancaveis;

Estados inalcançáveis podem ser removidos do AFD sem afetar a linguagem que ele aceita.

Estados Indistinguíveis

Algoritmo de Hopcroft

Um algoritmo para mesclar estados indistuinguíveis do AFD, elaborado por Hopcroft (1971). É baseado no refinamento de partição, no qual estados do AFD são particionados em grupos, de acordo com seu comportamento. Esses grupos representam classes de equivalência, como na relação de equivalência Myhill–Nerode, pela qual todo dois estados da mesma partição são equivalentes se eles têm o mesmo comportamento para todas as sequências de entrada. Isto é, para todo dois estados $p_{1}$ e $p_{2}$ que pertencem à mesma classe de equivalência da partição $P$, temos que para qualquer palavra de entrada $w$, ao seguir-se as transições determinadas por $w$ partindo dos estados $p_{1}$ e $p_{2}$, ambos os estados serão levados a estados de aceitação, ou ambos a estados de rejeição; não deveria ser possível a $w$ levar $p_{1}$ a um estado de aceitação e $p_{2}$ a um estado de rejeição, ou vice-versa.

O seguinte pseudocódigo descreve o algoritmo:

P:= {{todos estados de aceitação}}, {todos estados de não-aceitação}};
Q:= {{todos estados de aceitação}};
while (Q é não-vazio) do
     escolha e remova um conjunto A de Q
     for each c in ∑ do
          let X é o conjunto de estados para o qual uma transição sobre c leva a um estado em A
          for each conjunto Y in P para o qual X ∩ Y é não-vazio do
               substitua Y em P pelos dois conjuntos X ∩ Y e Y \ X
               if Y está contido em Q
                    substitua Y em Q pelos mesmos dois conjuntos
               else
                    adicione o menor dos dois conjuntos à Q
          end;
     end;
end;

O algoritmo inicia com uma partição grossa: todo par de estados equivalentes de acordo com relação Myhill-Nerode pertencem ao mesmo conjunto na partição, mas pares não-equivalentes ainda podem pertencer ao mesmo conjunto. O algoritmo gradualmente refina a partição em um número maior de conjuntos menores, em cada passo dividindo conjuntos de estados em pares de subconjuntos necessariamente não-equivalentes.

A partição inicial é uma separação dos estados em dois subconjuntos de estados que claramente não têm o mesmo comportamento:estados de aceitação e estados de rejeição. O algoritmo então repetidamente escolhe um conjunto $A$ da partição atual e um símbolo de entrada $c$, e divide cada um dos conjuntos da partição em dois subconjuntos: o subconjunto de estados que leva à $A$ através do símbolo de entrada $c$, e o subconjunto de estados que não leva a $A$. Como se sabe que $A$ tem comportamento diferente dos outros conjuntos da partição, os subconjuntos que levam a $A$ também têm comportamentos diferentes dos subconjuntos que não levam a $A$. Quando nenhuma outra divisão desse tipo pode ser encontrada, o algoritmo termina.

O tempo de execução do algoritmo no pior caso é $O(ns{\mbox{ }}\log n)$, onde $n$ é o número de estados e $s$ é o tamanho do alfabeto. Esse limite vem do fato que, para cada umas das $ns$ transições do autômato, os conjuntos tomados de $Q$ que contêm o estado alvo da transição têm tamanhos que decrescem relativamente entre si por um fator de dois ou mais, então cada transição participa em $O(\log n)$ dos passos de divisão no algoritmo. A estrutura de dados do refinamento de partição permite que cada passo de divisão seja feito em tempo proporcional ao número de transições que participam dele. Esse é o melhor algoritmo conhecido para resolver o problema da minimização de AFDs, e para certas distribuições de entradas sua complexidade do caso-médio é ainda melhor, $O(n{\mbox{ }}\log \log n)$.

Uma vez que o algoritmo de Hopcroft tenha sido usado para agrupar estados do AFD de entrada em classe de equivalência, o AFD mínimo pode ser construído formando um estado para cada classe de equivalência. Se $S$ é um conjunto de estados em $P$, $s$ é um estado em $S$, e $c$ é um caracter de entrada, então a transição no AFD mínimo do estado para $S$, sobre a entrada $c$, leva ao conjunto contendo o estado ao qual o autômato de entrada levaria partindo do estado $s$, sobre a entrada $c$. O estado inicial do AFD mínimo é o conjunto que contém o estado inicial do AFD de entrada, e os estados de aceitação do AFD mínimo são os conjuntos cujos membros são estados de aceitação no AFD de entrada.

Algoritmo de Moore

O algoritmo de Moore para minimização de AFD foi proposto por Moore (1956). Como o algoritmo de Hopcroft, ele mantém uma partição que inicia separando os estados de aceitação dos estados de rejeição, e repetidamente refina a partição até que nenhum outro refinamento possa ser efetuado. Em cada passo, ele substitui a partição atual com o refinamento mais grosso das $s+1$ partições, das quais uma é a atual e as outras são as pré-imagens da partição atual sob as funções de transição para cada um dos símbolos de entrada. O algoritmo termina quando essa substituição não muda a partição atual. A complexidade de tempo no pior caso é $O(n^{2}s)$: cada passo do algoritmo pode ser executado em tempo $O(ns)$ usando uma variante de radix sort para reordenar os estados tal que estados no mesmo conjunto da nova partição sejam consecutivos na ordenação, e haja no máximo $n$ passos já que todos menos o último passo aumentam o número de conjuntos na partição. Os exemplos do problema da minimização de AFD que causam o comportamento do pior caso são os mesmos que os para o algoritmo de Hopcroft. O número de passos que o algoritmo executa pode ser muito menor que $n$, então em média (para $s$ constante) seu desempenho é $O(n{\mbox{ }}\log n)$ ou até $O(n{\mbox{ }}\log \log n)$ dependendo da distribuição aleatória sobre o autômato escolhido para modelar o comportamento do caso médio do algoritmo.

Algoritmo de Brzozowski

Como Brzozowski (1963) observou, reverter as arestas de um AFD produz um AFN para a inversa da linguagem original, e convertendo este AFN para um AFD usando a construção do conjunto das partes padrão (construindo apenas os estados alcançáveis do AFD convertido) leva a um AFD mínimo para a mesma linguagem invertida. Repetindo essa operação inversa uma segunda vez produz um AFD mínimo para a linguagem original. A complexidade do pior caso do algoritmo de Brzozowski é exponencial, já que há linguagens regulares para as quais o AFD mínimo da inversa é exponencialmente maior do que o AFD mínimo da linguagem,, no entanto o algoritmo normalmente tem um desempenho melhor do que o pior caso sugeriria.

Minimização de AFN

Enquanto os procedimentos acima funcionam para AFDs, o método de particionamento não funciona para autômatos finitos não-determinísticos (AFNs). Encontrar um algoritmo de tempo polinomial que minimize AFNs é impossível, a menos que P=NP.

Bibliografia

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), «4.13 Partitioning», The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162 .
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), «Minimization of Automata», Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318 
• Brzozowski, J. A. (1963), «Canonical regular expressions and minimal state graphs for definite events», Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., pp. 529–561, MR 0175719 .
• Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), «State Complexity of Basic Operations on Finite Languages», 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6 .
• Hopcroft, John (1971), «An $n{\mbox{ }}\log n$ algorithm for minimizing states in a finite automaton», Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, pp. 189–196, MR 0403320 
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation 2nd ed. , Addison-Wesley .
• Leiss, Ernst (1981), «Succinct representation of regular languages by Boolean automata», Theoretical Computer Science, 13 (3): 323–330, MR 603263, doi:10.1016/S0304-3975(81)80005-9 .
• Moore, Edward F. (1956), «Gedanken-experiments on sequential machines», Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, pp. 129–153, MR 0078059 .

Ligações externas

• DFA minimization using the Myhill-Nerode theorem