Projecto de autómato finito determinista

Projete um AFD que reconheça as sequências definidas sobre o alfabeto A = {a;b;c} que satisfazem o requisito de qualquer b ter um a imediatamente à sua esquerda e um c imediatamente à sua direita.

Aproximação possível:

Note que para estar num estado final, caso apareça um símbolo b na entrada, é necessário garantir um estado prévio (a) e um estado seguinte (c).
Note também que esse estado seguinte é final (cumpre o requisito), o mesmo acontecendo com o estado inicial.
Temos assim a necessidade de pelo menos quatro estados (estado inicial, e os três estados correspondentes à sequência abc).
Por outro lado, caso apareça um símbolo b, sem que exista um a imediatamente à sua esquerda, ou um c imediatamente à sua direita, podemos desde logo afirmar que a entrada não cumpre o requirido pelo que precisamos de um estado que não seja final mas donde não seja possível sair (tipo “buraco negro”).

Chegamos assim ao seguinte AFD:

Será que podemos simplificar esta autómato?

Se compararmos os estados A e D, constata-se que são ambos finais e as transições para fora são equivalentes.

Logo podem ser fundidos:

Redução de autómatos finitos deterministas

Redução de AFD

O exemplo anterior mostra que por vezes é possível simplificar os AFD reduzindo o número de estados.

A ideia base é ter um procedimento sistemático para identificar estados equivalentes, fundindo-os num único estado.

Dois estados são equivalentes se forem do mesmo tipo (final ou não final) e se todas as suas transições para o exterior forem iguais (i.e. para os mesmos estados).

Considere o seguinte autómato:

Vamos primeiro aplicar a regra de fundir estados na mesma situação (mesmo tipo e transições iguais).

Olhando para a tabela de transições constata-se que os estados B e C são equivalentes:

Temos também equivalência nos estados D e E:

Agora há equivalência nos estados A e C:

Por fim há equivalência nos estados C e F:

Note que os estados E e G embora tendo as mesmas transições, não são equivalentes.

No entanto, este método para simplificar AFDs não garante um minimização total, já que não lida com o problema de poder haver ciclos entre estados equivalentes.

Esse problema é resolvido com o algoritmo que se apresenta a seguir.

Algoritmo de redução de AFD

Procedimento:

Primeiro divide-se os estados em dois conjuntos: o conjunto dos estados finais (aceitação) e o conjunto com os restantes estados.
Depois vai-se particionando sucessivamente os conjuntos existentes, sempre que dentro do conjunto existam estados que tenham transições com o mesmo símbolo para diferentes conjuntos.
O passo anterior é repetido até que não sejam possíveis mais partições. Nessa situação, o AFD está minimizado.

Recuperando o exemplo anterior, temos como conjuntos de partida:

C1 = Q - F = {A,B,C,D,E,F}
C2 = F = {G}

O conjunto C1 tem de ser partido em dois, já que para a entrada 1 os estados D e E têm uma transição para um conjunto diferente (C2) do que os restantes estados.

Chegamos assim a um AFD minimizado equivalente ao que já tínhamos chegado: