Minimização de estados

Muitas vezes é possível ter mais de um autômato reconhecendo o mesmo conjunto de sentenças, em geral através da presença de estados redundantes. O procedimento apresentado nesta seção permite detectar tais situações de redundância, reduzindo o número de estados do autômato ao mínimo possível.

O procedimento de minimização de estados de um autômato $M = (S, \Sigma, \delta, s_0, F)$ inicia-se pela criação de uma partição inicial $\Pi_0$ do conjunto de estados $S$ contendo dois subconjuntos, um com todos os estados finais, $F$, e outro contendo os estados não-finais, $S-F$.

O procedimento prossegue com o refinamento da partição corrente $\Pi_i$ para a criação de uma nova partição $\Pi_{i+1}$. Para tanto, analisa-se cada um dos conjuntos que compõem $\Pi_i$ buscando a criação de novas partições que sejam equivalentes sob transições. Partindo de cada grupo $G$ de estados em $\Pi_i$, um novo subgrupo $G'$ conterá dois estados $s$ e $t$ se e somente se, para todos os símbolos do alfabeto de entrada, $s$ e $t$ tenham transições para um mesmo grupo de $\Pi_i$.

A partir desse processo de refinamento dos grupos de $\Pi_i$, o conjunto dos subgrupos resultantes forma uma nova partição $\Pi_{i+1}$. O procedimento deve ser repetido até que a nova partição gerada seja igual à partição corrente, situação que indica que novos refinamentos não são mais possíveis.

Para construir o autômato com o número mínimo de estados, associa-se a cada subgrupo da partição final atingida por esse procedimento um estado da nova máquina $M'$. Eventualmente, o procedimento pode gerar ``estados mortos'', que não são estados finais e contêm transição apenas para si próprios, ou estados não-alcançáveis a partir do estado inicial. Tais estados podem ser eliminados do autômato resultante.

Aplicando esse procedimento ao autômato da Figura 3.5, tem-se que a partição inicial é

$$\Pi_0 = \{ \{s_0, s_1, s_2, s_3 \} , \{ s_4\} \}$$

A segunda partição, $G_2 = \{s_4\}$, é irredutível e não será mais analisada -- este será o estado final do autômato minimizado. Para aplicar o procedimento de refinamento à primeira partição, $G_1 = \{s_0, s_1, s_2, s_3 \}$, deve-se analisar para cada estado qual o grupo resultante pela transição para cada um dos dois símbolos do alfabeto, $a$ e $b$:

	$s_0$	$s_1$	$s_2$	$s_3$
a	$G_1$	$G_1$	$G_1$	$G_1$
b	$G_1$	$G_1$	$G_1$	$G_2$

Observa-se que o grupo $G_1$ pode ser particionado em dois novos grupos, $G_3 = \{s_0, s_1, s_2 \}$ e $G_4 = \{ s_3\}$. Assim, a nova partição a ser analisada é

$$\Pi_1 = \{\{s_0, s_1, s_2 \}, \{ s_3\}, \{ s_4\}\}$$

Novamente há um grupo que não pode ser mais reduzido, mas o grupo $G_3$ precisa ainda ser analisado. Aplicando novamente o procedimento de refinamento considerando a nova partição $\Pi_1 = \{G_3, G_4, G_2\}$, o resultado para o refinamento do grupo $G_3$ é

	$s_0$	$s_1$	$s_2$
a	$G_3$	$G_3$	$G_3$
b	$G_3$	$G_4$	$G_3$

Nesse grupo, $s_0$ e $s_2$ permanecem com comportamento equivalente, portanto fazem parte do mesmo grupo, $G_5$; porém, $s_1$ faz parte de um novo grupo $G_6$. Assim, a partição resultante é

$$\Pi_2 = \{\{s_0, s_2\} , \{ s_1 \}, \{ s_3\}, \{ s_4\}\}$$

Como $\Pi_1 \neq \Pi_2$, o grupo $G_5$ (o único que ainda pode ser refinado) precisa ser analisado. A análise dos estados desse grupo resulta em

	$s_0$	$s_2$
a	$G_6$	$G_6$
b	$G_5$	$G_5$

Como não há novo particionamento, o procedimento de refinamento está concluído. O resultado obtido é que o estado $s_2$ pode ser incorporado ao estado $s_0$, resultando no autômato equivalente com número mínimo de estados. Esse autômato é apresentado na Figura 3.6.

Figura: Autômato com número mínimo de estados que reconhece $(a\vert b)^*abb$