Next: Autómatos Finitos com transições Up: Autómatos Finitos Previous: Simulação do funcionamento de

Autómatos Finitos Não-Deterministas

Vamos agora introduzir a noção de escolha, isto é, introduzir não-determinismo. A definição de AFND (Autómato Finito Não-Determinista) coincide com a do AFD com a única excepção que é agora encarada como uma relação (em vez de uma função):


Significa então que dado um estado e um símbolo poderemos ter vários estados possíveis para onde ir. Isto corresponde, se quiserem, à noção de universos múltiplos que aparece nas histórias de ficção científica ou na interpretação dos ``muitos mundos'' da mecânica quântica. Claro que muitos argumentam que o universo é um sistema determinista, não obstante complexo, e por conseguinte cada acção ou ``escolha'' que fazemos é pré-determinada ou pré-destinada. Contudo, pelo que me toca, gosto sempre de pensar que temos escolhas e liberdade de escolha...
Mas a verdade é que podemos sempre construir um AFD, a partir de um AFND dado, que aceite exactamente a mesma linguagem. Trata-se de um teorema importante que não é muito difícil de perceber se pensarmos que estamos sempre a lidar com um número finito de estados. Não obstante esta equivalência, muitas vezes é muito mais fácil definir um AFND do que um determinista equivalente. Vejamos um exemplo.
Uma tarefa típica de um editor de texto é procurar uma dada sub palavra ou padrão no texto. Vamos assumir, por simplicidade, que o texto é constituído por palavras formadas apenas por a's e b's; e que o padrão que andamos à procura é ababa. O AFND



aceita todos os textos que contêm a sub palavra ababa. Definir um AFD que reconheça a mesma linguagem é talvez um pouco mais complicado (deve-o fazer, no entanto, como exercício -uma versão não determinista e uma versão determinista).
Havendo várias transições possíveis para o mesmo símbolo de entrada, como é que sabemos para onde ir? Uma solução consiste em seguir por um dos estados e, em caso de falha, efectuar um retrocesso (``backtracking''): o Prolog irá voltar ao ponto de ramificação e ``remover'' os símbolos aceites desde essa ramificação.
O AFND que construímos é descrito em Prolog como se segue:

 % definicao do AFND ababa
estadoInicial(ababa,0).
         estadoFinal(ababa,5).
         delta(ababa,0,a,0).
         delta(ababa,0,a,1).
         delta(ababa,0,b,0).
         delta(ababa,1,b,2).
         delta(ababa,2,a,3).
         delta(ababa,3,b,4).
         delta(ababa,4,a,5).
         delta(ababa,5,a,5).
         delta(ababa,5,b,5).

Temos agora que alterar o nosso reconhecedor de palavras para passar a funcionar com AFNDs. A versão que se segue funciona quer com autómatos deterministas quer com autómatos não deterministas (a única alteração foi a remoção do cut).

         aceita(AF,Palavra) :-
           estadoInicial(AF,I),
           reconhece(AF,Palavra,I). % estadoCorrente = estadoInicial

         reconhece(AF,[],EstCor) :-
           estadoFinal(AF,EstCor).
         reconhece(AF,[S|R],EstCor) :-
           delta(AF,EstCor,S,ProxEst),
           reconhece(AF,R,ProxEst).

Com estas definições obtemos:

         ?- aceita(ababa,[b,a,b,a,b,b,a,b,a,b,b,a,b,a,b,b,a]).
            no
         ?- aceita(ababa,[b,a,b,a,b,b,a,b,a,b,a,b,a,b,a,b,b,a]).
            yes

Next: Autómatos Finitos com transições Up: Autómatos Finitos Previous: Simulação do funcionamento de


1999-05-20