Программирование на языке Пролог для искусственного интеллекта
какой из возможных переходов делать
Решать, какой из возможных переходов делать в каждый момент времени - исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в
Рис. 4. 4. Допущение цепочки: (a) при чтении первого символа X;
(b) при совершении спонтанного перехода.
текущем состоянии. Однако абстрактные недетерминированные машины такого типа обладают волшебным свойством: если существует выбор, они всегда избирают "правильный" переход, т.е. переход, ведущий к допущению входной цепочки при наличии такого перехода. Автомат на рис. 4.3, например, допускает цепочки аb и aabaab, но отвергает цепочки abb и abba. Легко видеть, что этот автомат допускает любые цепочки, оканчивающиеся на а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).
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий