Next: Autómatos Finitos com
transições Up: Autómatos Finitos Previous:
Simulação do funcionamento de
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