Программирование на языке Пролог для искусственного интеллекта | страница 67
(1) он начинается в начальном состоянии,
(2) он оканчивается в конечном состоянии, и
(3) метки дуг, образующих этот путь, соответствуют полной входной цепочке.
Решать, какой из возможных переходов делать в каждый момент времени — исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в текущем состоянии. Однако абстрактные недетерминированные машины такого типа обладают волшебным свойством: если существует выбор, они всегда избирают "правильный" переход, т.е. переход, ведущий к допущению входной цепочки при наличии такого перехода. Автомат на рис. 4.3, например, допускает цепочки аb и aabaab, но отвергает цепочки abb и abba. Легко видеть, что этот автомат допускает любые цепочки, оканчивающиеся на аb и отвергает все остальные.
Рис. 4.4. Допущение цепочки: (a) при чтении первого символа X; (b) при совершении спонтанного перехода.
Некоторый автомат можно описать на Прологе при помощи трех отношений:
(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).
Представим входные цепочки в виде списков Пролога. Цепочка ааb будет представлена как >[а, а, b]. Модель автомата, получив его описание, будет обрабатывать заданную входную цепочку, и решать, допускать ее или нет. По определению, недетерминированный автомат допускает заданную цепочку, если (начав из начального состояния) после ее прочтения он способен оказаться в конечном состоянии. Модель программируется в виде бинарного отношения >допускается, которое определяет принятие цепочки из данного состояния. Так
>допускается( Состояние, Цепочка)
истинно, если автомат, начав из состояния >Состояние как из начального, допускает цепочку >Цепочка. Отношение >допускается можно определить при помощи трех предложений. Они соответствуют следующим трем случаям:
