Автоматы и пролог - PullRequest
Новая
       23

Автоматы и пролог

2 голосов
/ 21 апреля 2020

Я пытался сделать недетерминированные c конечные автоматы в PROLOG, вот мой код: 

state(1).
state(2).
state(3).

initial_state(1).
final_state(3).

alphabet(a).
alphabet(b).

delta(1, b, 2).
delta(2, a, 2).
delta(2, a, 3).
delta(3, b, 2).

accept([X|[]], Q) :- 
    alphabet(X),
    delta(Q, X, Q1),
    final_state(Q1).
accept([X|XS], Q) :- 
    alphabet(X),
    delta(Q, X, Q1),
    accept(XS, Q1).

Где accept - это функция, которая задает строку и состояние, она скажет нам, если это будет принято автоматом. Проблема в том, что когда я пытаюсь увидеть, принимается ли автоматом строка baba ([b, a, b, a]) (accept ([b, a, b, a], 1)), я получаю значение true, которое не правильно.

1 Ответ

2 голосов
/ 21 апреля 2020

почему вы думаете, что это не получится? Последовательность решения: 

delta(1, b, 2)
delta(2, a, 3)
delta(2, a, 2)
delta(2, a, 3)

Моя личная "лучшая практика" - собрать доказательства 

accept([X|[]], Q,[delta(Q, X, Q1)]) :- 
    alphabet(X),
    delta(Q, X, Q1),
    print(delta(Q, X, Q1)),nl,
    final_state(Q1).
accept([X|XS], Q,[delta(Q, X, Q1)|Rest]) :- 
    alphabet(X),
    delta(Q, X, Q1),
    print(delta(Q,X,Q1)),nl,
    accept(XS, Q1,Rest).
accept(String,State):-accept(String,State,_).

. Это показывает, что программа может быть проверена с помощью приведенной выше последовательности 

?- accept([b,a,b,a],1, Proof).
Proof = [delta(1, b, 2), delta(2, a, 3), delta(3, b, 2), delta(2, a, 3)]
...