Prolog #4: Задачи и примеры #2

Задача 4

1. Напишите предикат mem, который проверяет на принадлежность к списку[Как много параметров у него должно быть? Как можно использовать рекурсию? Есть предопределенный предикат member, который уже это выполняет]

Перед тем как двигаться дальше, рассмотрим еще одно применение списков. Использование конечного автомата очень распространено во многих видах компьютерных приложений. Что мы будем рассматривать, так это как имитировать конечный автомат, независимо от языка, который требуется распознать.

Процесс имитации включает в себя работу двух компонент. Во-первых, должен быть механизм описания автомата, т.е. его состояния и переходы. Во-вторых, мы должны определить предикат, который имитирует действие заданной машины. Определение машины включает в себя 3 компоненты: переходы между состояниями, начальное состояние, конечное состояние. Определение начального и конечного состояний достаточно легкое (как будет показано далее). Чтобы задать переход, мы должны задать для каждого состояния и входного символа состояние, в которое будет произведен переход. Вот пример:

start(s).
final(f1).
final(f2).
delta(s, a, q1).
delta(s, b, q2).
delta(q1, b, s).
delta(q1, a, f1).
delta(q2, a, s).
delta(q2, b, f2).

Можете ли вы нарисовать диаграмму для этого конечного автомата?

А теперь насчет симулятора (имитатора, но звучит хреново). Симулятор, между прочим, должен работать для любого конечного автомата, заданного тем способом, что мы воспользовались. Что мы хотим знать, так это каковы входные строки должен принимать этот автомат (то есть, как должна происходить посимвольная обработка ввода). Предикат accept нам подойдет. Мы хотим дать список символов этому предикату, и получить ответ, принимается ли заданная строка автоматом. Следующее определение – это легкий способ сделать это. Попробуйте его. Действия accept подвержены влиянию порядка компонент в delta? Поменяйте порядок, чтобы узнать.

accept(S) :- start(S), accept(Q, S). %%% Странно выглядит!!!?
accept(Q, [X|XS]) :- delta(Q, X, Q1), %%% Имеет ли смысл, что
accept(Q1, XS). %%% количество параметров, которое принимает accept
accept(F, []) :- final(F). %%% меняется?

Определение правила очень странное. Но если мы рассмотрим как работает Пролог, унифицируя запрос с головой правила (или факта), мы можем увидеть, что если мы введем запрос

| ?- accept([a, b, b, a]).

то он совпадет только с первым правилом. Ссылка на accept в теле этого клоза, однако, будет унифицироваться только с первым из вторых двух правил. Интересно! (нет) Это можно даже назвать некоторым видом перегрузки.

Задача 5

Интересной задачей является определение Пролог программы, которая определяет, является ли данный список палиндромом. Для того, чтобы быть более точным, задача состоит в том, чтобы определить palindrome так, чтобы он выдавал следующие результаты:

Есть несколько способов определить такой предикат, одно решение очень простое.

Подсказка: Думайте о конечном автомате, который имеет два состояния – q0 и q1.

• Определите два предиката palindrome – первый принимает один аргумент, а остальные принимают три: palindrome(q, X, S), где первый аргумент – это состояние,а остальные – это списки. Первый определен в терминах второго следующим образом {palindrome(Xs) :- palindrome(q0, Xs, []).
• В состоянии q0 удалите всё из списка X и добавьте их в S
• В состоянии q1 успех достигнут, когда головы двух списков совпадают – т.е. когда palindrome(q1, [X|Xs], [X|S]) истинен.

Задача – как появляется переход из состояния q0 в q1?