Prolog
Шрифт:
допускается( Состояние, Цепочка)
истинно, если автомат, начав из состояния Состояние как из начального, допускает цепочку Цепочка. Отношение допускается можно определить при помощи трех предложений. Они соответствуют следующим трем случаям:
(1) Пустая цепочка [ ] допускается из состояния S, если S - конечное состояние.
(2) Непустая цепочка допускается из состояния S, если после чтения первого
(3) Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, а затем допустить (всю) входную цепочку из S1. Такой случай иллюстрируется на рис. 4.4(b).
Эти правила можно перевести на Пролог следующим образом:
допускается( S, [ ]) :-
% Допуск пустой цепочки
конечное( S).
допускается( S, [X | Остальные]) :-
% Допуск чтением первого символа
переход( S, X, S1),
допускается( S1, Остальные).
допускается( S, Цепочка) :-
% Допуск выполнением спонтанного перехода
спонтанный( S, S1),
допускается( S1, Цепочка).
Спросить о том, допускается ли цепочка аааb, можно так:
?- допускается( S1, [a, a, a, b]).
yes (да)
Как мы уже видели, программы на Прологе часто оказываются способными решать более общие задачи, чем те, для которых они первоначально предназначались. В нашем случае мы можем спросить модель также о том, в каком состоянии должен находиться автомат в начале работы, чтобы он допустил цепочку аb:
?- допускается( S, [a, b]).
S = s1;
S = s3
Как ни странно, мы можем спросить также "Каковы все цепочки длины 3, допустимые из состояния s1?"
?- допускается( s1, [XI, Х2, X3]).
X1 = а
Х2 = а
Х3 = b;
X1 = b
Х2 = а
nо (нет)
Если мы предпочитаем, чтобы допустимые цепочки выдавались в виде списков, тогда наш вопрос следует сформулировать так:
?- Цепочка = [ _, _, _ ], допускается( s1, Цепочка).
Цепочка = [а, а, b];
Цепочка = [b, а, b];
nо (нет)
Можно проделать и еще некоторые эксперименты, например спросить: "Из какого состояния автомат допустит цепочку длиной 7?"
Эксперименты могут включать в себя переделки структуры автомата, вносящие изменения в отношения конечное, переход и спонтанный. В автомате, изображенном на рис. 4.3, отсутствуют циклические "спонтанные пути" (пути, состоящие только из спонтанных переходов). Если на рис. 4.3 добавить новый переход
спонтанный( s1, s3)
то получится "спонтанный цикл". Теперь наша модель может столкнуться с неприятностями. Например, вопрос
?- допускается( s1, [а]).
приведет к тому, что модель будет бесконечно переходить в состояние s1, все время надеясь отыскать какой-либо путь в конечное состояние.
Упражнения
4. 4. Почему не могло возникнуть зацикливание модели исходного автомата на рис. 4.3, когда в его графе переходов не было "спонтанного цикла"?
Посмотреть ответ
4. 5. Зацикливание при вычислении допускается можно предотвратить, например, таким способом: подсчитывать число переходов, сделанных к настоящему моменту. При этом модель должна будет искать пути только некоторой ограниченной длины. Модифицируйте так отношение допускается. Указание: добавьте третий аргумент - максимально допустимое число переходов:
допускается( Состояние, Цепочка, Макс_переходов)
Посмотреть ответ
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
4. 4. Планирование поездки
В данном разделе мы создадим программу, которая дает советы по планированию воздушного путешествия. Эта программа будет довольно примитивным советчиком, тем не менее она сможет отвечать на некоторые полезные вопросы, такие как:
По каким дням недели есть прямые рейсы из Лондона в Любляну?
Как в четверг можно добраться из Любляны в Эдинбург?