Магазинный автомат SWI Prolog

Формулировка задачи:

Здравствуйте, стоит сложное задание, не могу сам справиться, даже не знаю с чего начать:

Определить недетерминированый магазинный автомат, распознающий язык, в котором за цепочкой из N символов A следует N символов B.

Помогите пожалуйста.

Решение задачи: «Магазинный автомат SWI Prolog»

Листинг программы

% automat(+State, +Input, +Stack)
 
% состояние 0
automat(0, [H|T], S) :-
    % какие-то проверки H
    automat(0, T, [H|S]).   % - в том же состоянии, стек растет
automat(0, [H|T], [HS|TS]) :-
    % какие-то другие проверки H и HS
    automat(1, T, TS).   % - в новом состоянии, стек снимается
 
% состояние 1
automat(1, [H|T], [HS|TS]) :-
    % какие-то третьи проверки H и HS
    automat(1, T, TS).   % - в прежнем состоянии, стек снимается
automat(1, [], []).  % - в этом состоянии возможен успешный выход        
                          % при исчерпании входной строки и стека

Объяснение кода листинга программы

Код представляет собой реализацию автомата (часто именуемого «машинным автоматом» или «автоматом ввода-вывода») на основе языка программирования SWI Prolog. Ниже приведено описание работы автомата в виде списка:

Состояние 0:
- При входной строке [H|T] и стеке S, где H — символ, а T — список символов, и при выполнении некоторых проверок на H:
  - В том же состоянии, стек растет. То есть [H|S] добавляется в стек.
  - При выполнении других проверок на H и HS (где HS — верхний элемент стека):
    - Переход в новое состояние, стек снимается. То есть [HS|TS] становится новым стеком.
- При входной строке [H|T] и пустом стеке [HS|TS], где H — символ, а T — список символов, и при выполнении некоторых проверок на H и HS:
  - В прежнем состоянии, стек снимается. То есть [HS|TS] становится новым стеком.
  - При исчерпании входной строки и стека:
    - Возможен успешный выход из автомата.
Состояние 1:
- При входной строке [H|T] и стеке [HS|TS], где H — символ, а T — список символов, и при выполнении некоторых проверок на H и HS:
  - В прежнем состоянии, стек снимается. То есть [HS|TS] становится новым стеком.
Условие успешного выхода из автомата:
- При входной строке [] (пустой строке) и стеке [HS|TS]:
  - Возможен успешный выход из автомата.