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




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


        спонтанный( S3, S1).

Представим входные цепочки в виде списков Пролога. Цепочка  ааb  будет представлена как [а, а, b]. Модель автомата, получив его описание, будет обрабатывать заданную входную цепочку, и решать, допускать ее или нет. По определению, недетерминированный автомат допускает заданную цепочку, если (начав из начального состояния) после ее прочтения он способен оказаться в конечном состоянии. Модель программируется в виде бинарного отношения допускается, которое определяет принятие цепочки из данного состояния. Так

        допускается( Состояние, Цепочка)

истинно, если автомат, начав из состояния Состояние как из начального, допускает цепочку Цепочка. Отношение допускается можно определить при помощи трех предложений. Они соответствуют следующим трем случаям:

(1)        Пустая цепочка [ ] допускается из состояния S, если S - конечное состояние.

(2)        Непустая цепочка допускается из состояния S, если после чтения первого ее символа автомат может перейти в состояние S1, и оставшаяся часть цепочки допускается из S1. Этот случай иллюстрируется на рис. 4.4(а).

(3)        Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, а затем допустить (всю) входную цепочку из S1. Такой случай иллюстрируется на рис. 4.4(b).

Эти правила можно перевести на Пролог следующим образом:

        допускается( S, [ ]) :-
                               % Допуск пустой цепочки
              конечное( S).

        допускается( S, [X | Остальные]) :-
                               % Допуск чтением первого символа



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