Analisador AFD em Prolog

O programa a seguir simula um analisador/aceitador para um autômato finito determinístico arbitrário (AFD). Quando este e um programa de tabela de estado são carregados no Prolog, o analisador/aceitador pode ser usado para verificar as entradas para o DFA para ver se são ou não aceitáveis. O programa rastreia sua ação usando instruções de escrita; estes foram recuados para melhor exibir a estrutura lógica das cláusulas.

parse(L) :- start(S), 
            trans(S,L).

trans(X,[A|B]) :- 
      delta(X,A,Y),   /*  X ---A---> Y */
      write(X),
      write('  '),
      write([A|B]),
      nl,
      trans(Y,B).  
trans(X,[]) :- 
      final(X),
      write(X),
      write('  '),
      write([]), nl.

Como exemplo, o seguinte código do Prolog especifica uma tabela de estado para um AFD que aceita o idioma (a,b)*ab(a,b)*.

delta(0,a,1).   
delta(0,b,0).
delta(1,a,1).
delta(1,b,2).
delta(2,a,2).
delta(2,b,2).
 
start(0).

final(2).

Um diagrama de estado para esta máquina é o seguinte:

Fig. 2.14

Suponha que o programa de controle e o programa de tabela de estado sejam carregados ...

?- parse([b,b,a,a,b,a,b]).
0  [b,b,a,a,b,a,b]
0  [b,a,a,b,a,b]
0  [a,a,b,a,b]
1  [a,b,a,b]
1  [b,a,b]
2  [a,b]
2  [b]
2  []
yes

?- parse([b,b,a]).
0  [b,b,a]
0  [b,a]
0  [a]
no

Exercício 2.14 Modifique o arquivo 'dfadrivr.pro' para que ele se torne um analisador de autômatos finitos não determinísticos (AFNs). Por que essa extensão é tão natural para Prolog?

Exercício 2.15 Usando o simulador AFD apresentado aqui como motivação, projete um simulador Prolog para máquinas de Turing.

Veja Também

• Código do Prolog para esta seção.
• 2.15 Estruturas e caminhos em grafos em Prolog
• Prolog Tutorial Sumário