Last updated
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:
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.
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:
Considere o seguinte autómato para reconhecer frases tipo ah! ah!:
