Магазинный автомат SWI Prolog
Формулировка задачи:
Здравствуйте, стоит сложное задание, не могу сам справиться, даже не знаю с чего начать:
Помогите пожалуйста.
Определить недетерминированый магазинный автомат, распознающий язык, в котором за цепочкой из N символов A следует N символов B.
Решение задачи: «Магазинный автомат SWI Prolog»
textual
Листинг программы
- % 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] становится новым стеком.
- При исчерпании входной строки и стека:
- Возможен успешный выход из автомата.
- При входной строке [H|T] и стеке S, где H — символ, а T — список символов, и при выполнении некоторых проверок на H:
- Состояние 1:
- При входной строке [H|T] и стеке [HS|TS], где H — символ, а T — список символов, и при выполнении некоторых проверок на H и HS:
- В прежнем состоянии, стек снимается. То есть [HS|TS] становится новым стеком.
- При входной строке [H|T] и стеке [HS|TS], где H — символ, а T — список символов, и при выполнении некоторых проверок на H и HS:
- Условие успешного выхода из автомата:
- При входной строке [] (пустой строке) и стеке [HS|TS]:
- Возможен успешный выход из автомата.
- При входной строке [] (пустой строке) и стеке [HS|TS]:
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д
