(1) Пустая цепочка >[] допускается из состояния S, если S — конечное состояние.
(2) Непустая цепочка допускается из состояния S, если после чтения первого ее символа автомат может перейти в состояние S1, и оставшаяся часть цепочки допускается из S1. Этот случай иллюстрируется на рис. 4.4(а).
(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, [X1, Х2, X3]).
>X1 = а
>X2 = а
>X3 = b;
>X1 = b
>X2 = а
>X3 = b;
>nо (нет)
Если мы предпочитаем, чтобы допустимые цепочки выдавались в виде списков, тогда наш вопрос следует сформулировать так:
>?- Цепочка = [ _, _, _ ], допускается( s1, Цепочка).
>Цепочка = [а, а, b];
>Цепочка = [b, а, b];
>nо (нет)
Можно проделать и еще некоторые эксперименты, например спросить: "Из какого состояния автомат допустит цепочку длиной 7?"
Эксперименты могут включать в себя переделки структуры автомата, вносящие изменения в отношения >конечное, >переход и >спонтанный. В автомате, изображенном на рис. 4.3, отсутствуют циклические "спонтанные пути" (пути, состоящие только из спонтанных переходов). Если на рис. 4.3 добавить новый переход
>спонтанный( s1, s3)
то получится "спонтанный цикл". Теперь наша модель может столкнуться с неприятностями. Например, вопрос
>?- допускается( s1, [а]).
приведет к тому, что модель будет бесконечно переходить в состояние s1, все время надеясь отыскать какой-либо путь в конечное состояние.
Упражнения
4.4. Почему не могло возникнуть зацикливание модели исходного автомата на рис. 4.3, когда в его графе переходов не было "спонтанного цикла"?
