Решать, какой из возможных переходов делать в каждый момент времени - исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в
Рис. 4. 4. Допущение цепочки: (a) при чтении первого символа X;
(b) при совершении спонтанного перехода.
текущем состоянии. Однако абстрактные недетерминированные машины такого типа обладают волшебным свойством: если существует выбор, они всегда избирают 'правильный' переход, т.е. переход, ведущий к допущению входной цепочки при наличии такого перехода. Автомат на рис. 4.3, например, допускает цепочки
Некоторый автомат можно описать на Прологе при помощи трех отношений:
(1) Унарного отношения конечное, которое определяет конечное состояние автомата.
(2) Трехаргументного отношения переход, которое определяет переход из состояния в состояние, при этом
переход( S1, X, S2)
означает переход из состояния S1 в S2, если считан входной символ X.
(3) Бинарного отношения
спонтанный( S1, S2)
означающего, что возможен спонтанный переход из S1 в S2.
Для автомата, изображенного на рис. 4.3, эти отношения будут такими:
конечное( S3).
переход( S1, а, S1).
переход( S1, а, S2).
переход( S1, b, S1).
переход( S2, b, S3).
переход( S3, b, S4).
спонтанный( S2, S4).
спонтанный( S3, S1).
Представим входные цепочки в виде списков Пролога. Цепочка
допускается( Состояние, Цепочка)
истинно, если автомат, начав из состояния Состояние как из начального, допускает цепочку Цепочка. Отношение допускается можно определить при помощи трех предложений. Они соответствуют следующим трем случаям:
(1) Пустая цепочка [ ] допускается из состояния S, если S - конечное состояние.
(2) Непустая цепочка допускается из состояния S, если после чтения первого ее символа автомат может перейти в состояние S1, и оставшаяся часть цепочки допускается из S1. Этот случай иллюстрируется на рис. 4.4(а).
(3) Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, а затем допустить (всю) входную цепочку из S1. Такой случай
