Next: AFDs com acções semânticas Up: Autómatos Finitos Previous: Introdução

Autómatos Finitos Deterministas

Um autómato finito determinista (AFD) é definido como um quíntuplo

onde E é o conjunto (finito) de estados admissíveis; S o conjunto dos símbolos de entrada; a função de transição; o estado inicial; e o conjunto dos estados finais (não vazio). No exemplo da televisão dado acima, ; ; , ; i = off; e .
Consideremos agora um exemplo formal. Seja definido por ; ; , , ; i = 0; e . AFD₁ pode ser representado pelo seguinte diagrama:



onde convencionamos indentificar o estado inicial com uma seta dupla e os estados finais com um círculo duplo. Em Prolog basta-nos descrever este diagrama:

         estadoInicial(afd1,0).
         estadoFinal(afd1,2).
         delta(afd1,0,a,1).
         delta(afd1,1,a,2).
         delta(afd1,2,a,0).

Nos dois exemplos que vimos, as funções de transição são ambas totais. Como função que é, pode, no entanto, ser parcial. Discutiremos isto mais à frente. Os AFDs podem ser usados para ler palavras de entrada e terminar com a sua aceitação ou rejeição: eles são reconhecedores. Para compreender como os AFDs fazem este reconhecimento, convém olhá-los como sendo máquinas (computadores primitivos). Seja um AFD e consideremos uma fita de entrada (ou ficheiro de entrada), uma cabeça de leitura e um estado corrente. A função de transição será o análogo de um programa; e o estado corrente o análogo da instrução corrente a ser executada. A fita de entrada contém uma palavra, um símbolo em cada célula da fita. Teremos tantas células na fita quantos os símbolos na palavra de entrada. Dada uma palavra x inicializamos a ``máquina'' da seguinte maneira:

(i)

Colocamos x na fita de entrada -um símbolo por célula.

(ii)

A cabeça de leitura é posicionada na célula mais à esquerda (no primeiro símbolo da palavra de entrada).

(iii)

Colocamos i como estado corrente.

A máquina começa então a trabalhar. Como qualquer computador, ela tem um modo de funcionamento. Este computador funciona assim:

(i)

O símbolo que se encontra na célula apontada pela cabeça de leitura é lido (símbolo corrente). Se a fita já tiver acabado a máquina pára (o que acontece quando já tivermos lido toda a palavra).

(ii)

O próximo estado é calculo a partir do estado corrente e do símbolo corrente, usando a função de transição do autómato:

(iii)

A cabeça de leitura move-se uma célula para a direita.

(iv)

O proximoEstado torna-se no estadoCorrente, e torna-se ao passo (i).

Para clarificar o que acabámos de dizer, voltemos ao autómato AFD₁ e consideremos, como input, a palavra aa. No início, estadoCorrente=0 e cabeça de leitura está a apontar para o primeiro a:



Uma vez que delta(0,a)=1, o próximo estado passa a ser 1 e a cabeça de leitura passa a apontar para o segundo a:



Atendendo que e que a palavra de entrada só possui dois símbolos, o autómato termina na seguinte situação:



Como o autómato terminou num estado final, dizemos que a palavra aa é aceite (ou reconhecida) por AFD₁. O conjunto de todas as palavras aceites por um AFD é designado por linguagem aceite, linguagem definida ou linguagem reconhecida por esse autómato. As palavras aa e aaaaa são aceites por AFD₁ enquanto a palavra vazia, a palavra a e aaaa são rejeitadas. Não é muito difícil provar que a linguagem aceite por AFD₁ é dada pelo conjunto

Em Prolog o processo de reconhecimento de palavras por um AFD, que acabámos de explicar, pode ser descrito da seguinte maneira:

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

         reconhece(AFD,[],EstCor) :-
           estadoFinal(AFD,EstCor).
         reconhece(AFD,[S|R],EstCor) :-
           delta(AFD,EstCor,S,ProxEst), !, % reparar no cut
reconhece(AFD,R,ProxEst). % (delta 'e uma funcao...)

Com este programa poderemos perguntar ao interpretador de Prolog se uma palavra pertence, ou não, à linguagem definida por um determinado autómato. Por exemplo:

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

Quando a função de transição é total, qualquer palavra de entrada será lida na totalidade antes do AFD parar. Se a função de transição não for total isso não é assim. Esta classificação das funções de transição, conduz à correspondente classificação dos AFDs: se a função de transição de um AFD é total dizemos que o autómato é completo senão dizemos que ele é incompleto. Não é muito difícil pensarmos num método que permita transformar qualquer AFD incompleto num completo, ao mesmo tempo que preservamos a sua linguagem. Seja um AFD incompleto, isto é, existe um par para o qual não está definido. Vamos construir AFD', que é um AFD completo com a mesma linguagem de AFD, da seguinte maneira. Adicionamos um novo estado c a E e definimos de tal modo que para todo o e para todo o , se está definido e caso contrário. Para completar a função de transição , fazemos para todo o . é um autómato com as características desejadas.
No nosso próximo exemplo vamos considerar uma linguagem na qual certas combinações de letras são proibidas. Pretendemos construir um AFD que reconheça essa linguagem. Consideramos e a linguagem L formada por todas as palavras com símbolos em S que não contêm dois a's consecutivos. Qualquer palavra que não contenha o símbolo a está trivialmente em L: a palavra vazia, b, bb, ..., bⁱ, ... A palavra a também está em L, mas as palavras

concerteza que não. Exemplos de mais palavras que estão em L são:

O autómato seguinte define a linguagem L.

Next: AFDs com acções semânticas Up: Autómatos Finitos Previous: Introdução