Конечные государственные автоматы в прологе

Question

Программа на Прологе, описывающая конечные автоматы. Необходимо иметь 2 списка аргументов, первый, например, содержащий входные данные ([a, b, a, b, a]), а другой - выходные данные. возвратитесь через состояния, через которые он прошел, следуя стрелкам, например [1,3,2,4,5]

Answer 1

Предполагается, что вы кодируете свои автоматы конечного состояния с помощью предикатов f(StartState, EdgeLabel, EndState):

f(1,a,2).  f(1,b,1).
f(2,a,3).  f(2,b,4).
f(3,a,5).  f(3,b,2).
f(4,a,5).  f(4,b,1).
f(5,a,3).  f(5,b,1).

Ответ на этот вопрос для фиксированной последовательности действий можно выполнить, просто связав запросы к f/3:

?- X1=1, f(X1,a,X2), f(X2,b,X3), f(X3,a,X4), f(X4,b,X5), f(X5,a,X6), L=[X1,X2,X3,X4,X5,X6].
L = [1, 2, 4, 5, 1, 2] .

Ответ на один и тот же запрос для списка действий можно выполнить рекурсивно.

Базовый шаг прост: если вы начинаете с Start и не применяете никаких действий ([]), посещенные состояния: [Start].

walk(Start, [], [Start]).

Если у вас есть последовательность действий и последовательность посещенных состояний, из Start мы применяем действие Input и достигаем состояния State, и делаем рекурсивно то же самое с остальными действиями Inputs а остальные состояния States:

walk(Start,[Input|Inputs],[Start|States]) :-
    f(Start,Input,State),
    walk(State, Inputs, States).

Тест:

?- walk(1, [a,b,a,b,a], X).
X = [1, 2, 4, 5, 1, 2] ;
false.