Next: Exercícios Up: Autómatos Finitos Previous: Autómatos Finitos Não-Deterministas
Nos autómatos que vimos até agora, exigimos, em cada passo, que a cabeça de leitura
se mova uma célula para a direita. Vamos agora relaxar esta condição permitindo que a
cabeça permaneça na mesma célula durante uma transição. A estas transições, às
quais não correspondem nenhum símbolo lido, chamamos transições vazias. Num
AFND com transições vazias temos
Para que o nosso programa Prolog aceite estes autómatos, basta acrescentar uma terceira cláusula reconhece/3:
reconhece(AF,T,EstCor) :-
transicaoVazia(AF,EstCor,ProxEst),
reconhece(AF,T,ProxEst).
O poder expressivo de um AFND com transições vazias não é maior que um AFND (que
por sua vez é igual, como dissemos, a um AFD). Existem situações, no entanto, em que as
transições vazias são úteis. Vejamos alguns exemplos.
Dados dois autómatos AF1 e AF2, pretende-se construir
um terceiro autómato AFtv que defina a linguagem dada pela união da
linguagem reconhecida por AF1 com a linguagem reconhecida por AF2.
O autómato AFtv pretendido pode ser definido com um novo estado inicial
que, via transições vazias, conduz aos estados iniciais de AF1 e AF2.
Com esta construção vê-se facilmente que se x é uma palavra aceite por AF1,
então x é aceite por AFtv e que se x é aceite por AF2,
então é aceite por AF3. O inverso também é verdade: se x é
aceite por AF3 é aceite por AF1 ou por AF2.
Vejamos, para terminar, um autómato finito com transições vazias que define um número
decimal sem sinal
e a respectiva definição em Prolog
digitos([0,1,2,3,4,5,6,7,8,9]).
estadoInicial(af_tv,1).
estadoFinal(af_tv,4).
delta(af_tv,1,D,2) :- digitos(L), member(D,L).
delta(af_tv,2,.,3).
delta(af_tv,3,D,4) :- digitos(L), member(D,L).
transicaoVazia(af_tv,2,1).
transicaoVazia(af_tv,2,4).
transicaoVazia(af_tv,4,3).
que nos permite fazer perguntas como as que se seguem.
?- aceita(af_tv,[1,1,.,2,3]). % 11.23
yes
?- aceita(af_tv,[.,2,3]). % .23
no
?- aceita(af_tv,[2,3]). % 23
yes
Next: Exercícios Up: Autómatos Finitos Previous: Autómatos Finitos Não-Deterministas