Программирование на языке ПРОЛОГ для искуственного интеллекта




Моделирование недетерминированного автомата - часть 2


Решать, какой из возможных переходов делать в каждый момент времени - исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в

fig4_4.gif (2270 bytes)

Рис. 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).

        спонтанный( S2, S4).



Содержание  Назад  Вперед