Minimização de autômatos

Por minimização de um autômato entendemos encontrar um autômato equivalente que contenha o menor número possível de estados. Mesmo um autômato que não contém nenhum estado inútil pode ser simplificado ainda mais.

Exemplo

Tome este autômato:

o autômato aceita apenas as palavras 01 e 11. É evidente que existe um autômato mais simples, com três estados, que aceita a mesma linguagem. Os estados q₁ e q₂ podem ser fundidos em um novo estado {q₁, q₂}, e as transições que levavam aos estados q₁ ou q₂ passarão a levar ao novo estado, e o mesmo vale para as transições que saíam de q₁ e q₂. Obtemos este autômato:

Esse autômato claramente aceita a mesma linguagem que o anterior e, ao mesmo tempo, tem menos estados.

Equivalência de estados

Considere um autômato A = ⟨Q, Σ, δ, q₀, F⟩. Definimos a linguagem do estado q ∈ Q, que denotamos por L(q), como

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Isto é, mudamos o estado inicial do autômato A de q₀ para q e calculamos a linguagem aceita por esse autômato. Em outras palavras, na linguagem L(q) estão todas as palavras w tais que, no autômato A, a partir do estado q, com a palavra w, chegamos a um estado final do autômato. Voltando ao autômato anterior, temos L(q₁) = {1}.

Dizemos que dois estados distintos q₁ e q₂ são equivalentes se vale

$L (q_{1}) = L (q_{2})$

O que isso significa? Se os estados q₁, q₂ são equivalentes, então, se fizermos deles estados iniciais do autômato, eles gerarão a mesma linguagem. Em outras palavras: se o autômato chega às configurações ⟨q₁, w⟩ e ⟨q₂, w⟩, então nos dois casos ele deve aceitar ou, nos dois casos, rejeitar.

Voltando ao autômato anterior: os estados q₁ e q₂ são equivalentes, porque, se estamos no estado q₁, só podemos aceitar a palavra de entrada se a parte não lida da palavra for igual a 1. O mesmo vale se estamos no estado q₂.

Na minimização de um autômato, trata-se, portanto, de encontrar estados equivalentes e eliminá-los, fundindo-os em um único novo estado, como fizemos no exemplo acima.

Como encontrar estados equivalentes

Que estados certamente não serão equivalentes? Se tomarmos um estado final e um estado não final, eles certamente não serão equivalentes, porque a linguagem do estado final é diferente da linguagem do estado não final — o estado final com certeza aceita a palavra ε, e o não final, não. Vamos mostrar o procedimento logo em um exemplo. Considere este autômato:

Começamos criando dois conjuntos de estados

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Agora criamos a tabela de transições e mantemos a informação sobre os grupos S₁ e S₂:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Agora modificamos a tabela de modo que, em vez de ter escrito diretamente para quais estados se vai com o símbolo dado, anotamos ali apenas o grupo para o qual passamos. Por exemplo, do estado q₃, com 0, chegamos ao estado q₅, que está no grupo S₂. Em vez de q₅, escrevemos, então, na tabela S₂:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Agora dividimos os dois grupos mais uma vez. Colocamos nos mesmos grupos sempre os estados que passam para os mesmos grupos para todos os símbolos. Por exemplo, os estados q₃ e q₆ não ficarão no mesmo grupo, porque nem com 0 nem com 1 vão para o mesmo grupo. Já os estados q₁ e q₂ ficarão no mesmo grupo, porque nenhum dos dois tem transição para 0 e ambos vão, com 1, para o grupo S₁. Criamos, assim, novos grupos:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Em cada grupo temos as mesmas transições. Rotulamos os grupos recém-criados e de novo descobrimos para qual desses novos grupos os estados apontam:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Neste momento faríamos outra divisão dos grupos. Mas vemos que não podemos fazer mais nenhuma divisão, porque obteríamos os mesmos grupos — pois os estados q₁ e q₂ têm, de fato, as mesmas transições dentro dos grupos, mas já estão no mesmo grupo, e nenhum outro estado está no grupo S₄. O algoritmo de busca de estados equivalentes chegou ao fim. De cada grupo basta escolher um estado; apagamos os outros, e todas as transições que levavam aos estados apagados passarão a levar ao único estado que escolhemos.

Podemos escolher, assim, que o nosso novo autômato terá os estados q₃, q₆, q₀, q₁, q₄ e removemos os estados q₂ e q₅. Todas as transições que levavam a q₂ agora levarão a q₁, e todas as transições que levavam a q₅ levarão a q₄:

Procedimento de minimização de um autômato

Removemos os estados inacessíveis,
removemos os estados inúteis,
removemos os estados equivalentes.

Fontes

Capítulos: Estados inacessíveis, Estados inúteis, Minimização de autômatos

« Anterior: Estados inúteis

Próximo: Propriedades de fecho das linguagens regulares »