Minimização de Autômatos Finitos Determinísticos

Este tópico pertence ao estudo de Linguagens Formais e Teoria da Computação, mas também aparece em outras áreas, como a Eletrônica Digital. Apesar de importante, muitas vezes acaba sendo deixado de lado devido prazos curtos para o ensino de um dado conteúdo o que muitas vezes resulta em um não aprofundamento de muitos tópicos, mas aqui vai uma leve introdução deste.

Ele visa o seguinte: dado um AFD qualquer, nosso objetivo é encontrar outro que faça a mesma coisa, porém com o mínimo de estados possível.

Para isso, temos que discutir sobre alguns tópicos diferentes. Vamos começar com equivalência de estados.

Equivalência de Estados

Dizemos que dois estados distintos p e q são equivalentes se, para toda string w, o estado alcançado a partir de p ao processar w é de aceitação se e somente se o estado alcançado a partir de q também for de aceitação.

Em outras palavras:

Para toda string w, δ̂(p, w) é um estado de aceitação se, e somente se, δ̂(q, w) também for um estado de aceitação.

Observe que, nessa definição, os estados finais alcançados ao processar a string w a partir de p e q não precisam ser iguais — basta que sejam ambos de aceitação.

A intuição por trás disso é simples: não conseguimos distinguir dois estados p e q se toda string que leva p a um estado final também leva q a um estado final.

Dessa definição também conseguimos intuir o que seria uma condição para diferenciar dois estados: basta que exista alguma string w que leve p a um estado final, mas não leve q a um estado final.

Exemplo

Na imagem do autômato, temos que, por exemplo, A e G são dois estados diferentes, pois a string 01 leva A para um estado final C, mas não leva G para um estado final (E).

Essa condição é suficiente para dizer que os dois estados são diferentes.

Agora observe o par A e E. Sabemos que eles são candidatos a serem equivalentes, pois ambos não são estados finais. Além disso, sabemos também que toda e qualquer string da forma w = 1x não consegue distingui-los, já que ambas as cadeias vão levar ao estado F, e a partir daí o comportamento é idêntico.

Mas analisar todas as strings possíveis dá trabalho — teríamos que fazer esse processo para cada par, o que seria muito custoso computacionalmente.

É aí que vem uma ideia que, apesar de simples, é extremamente eficaz para encontrar quais pares são equivalentes ou não dentro de um AFD.

Detecção de Pares Equivalentes

A base da nossa hipótese indutiva é bem simples:

Dado um par (p, q) de estados, eles são distinguíveis se p for um estado final e q não for.

Isso é intuitivo — se um aceita a string vazia (λ) e o outro não, eles são diferentes.

Nossa indução gira em torno disso:

Se existe um símbolo a tal que δ(j, a) = p e δ(k, a) = q, e o par (p, q) é distinguível, então o par (j, k) também será distinguível. Parece até meio bobo mas de verdade é apenas isso.

Processo Algorítmico

Para detectar todos os pares que são diferentes, montamos uma matriz com todos os estados.

Cada célula (p, q) é marcada com um “X” se os estados forem distinguíveis.

Na matriz correspondente ao autômato mostrado acima, começamos preenchendo toda a coluna e linha que envolvem o estado C, pois ele é o único estado final — logo, é diferente de todos os outros.

Podemos olhar, por exemplo, para o par (A, D):

δ(A, 0) = B e δ(D, 0) = C.

Sabemos que B e C são diferentes, então A e D também são.

Esse processo é repetido para todos os pares até que não seja possível identificar mais nenhum novo par distinguível.

Os pares sem X são considerados equivalentes no autômato.

Observação: a equivalência é transitiva.

Se j é equivalente a k e k é equivalente a p, então j é equivalente a p.

Construindo o Autômato Mínimo

Agora que sabemos quais estados são equivalentes, basta fundir cada grupo de estados equivalentes em um único estado, mantendo suas transições para os outros estados equivalentes.

O resultado é o autômato mínimo — equivalente ao original, mas com o menor número possível de estados.

Conclusão

Com esse processo, espero que tenham conseguido compreender a ideia por trás da minimização de autômatos finitos determinísticos.

Ainda há muito o que estudar, como provar formalmente que o autômato obtido é realmente o menor possível e por que ele não pode ser minimizado ainda mais, mas a intuição básica espero que tenham entendido bem.

Referência:

Hopcroft, Motwani e Ullman — Introduction to Automata Theory, Languages and Computation (2ª edição)

SAPERE AUDE!