Prolog

Использование отношений-селекторов облегчает также и последующую модификацию программ. Представьте себе, что мы захотели повысить эффективность программы, изменив представление информации. Все, что нужно сделать для этого, - изменить определения отношений-селекторов, и вся остальная программа без изменений будет работать с этим новым представлением.

Упражнение

4. 3.    Завершите определение отношения nребенок, определив отношение

        n_элемент( N, Список, X)

которое выполняется, если Х является N-м элементом списка Список.

Посмотреть ответ

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

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

4. 3.    Моделирование недетерминированного автомата

Данное упражнение показывает, как абстрактную математическую конструкцию можно представить на Прологе. Кроме того, программа, которая получится, окажется значительно более гибкой, чем предполагалось вначале.

Недетерминированный конечный автомат - это абстрактная машина, которая читает символы из входной цепочки и решает, допустить или отвергнуть эту цепочку. Автомат имеет несколько состояний и всегда находится в одном из них. Он может изменить состояние, перейдя из одного состояния в другое. Внутреннюю структуру такого автомата можно представить графом переходов, как показано на рис. 4.3. В этом примере S₁, S₂,   S₃  и  S₄  - состояния автомата. Стартовав из начального состояния (в нашем примере это S₁ ), автомат переходит из состояния в состояние по мере чтения входной цепочки. Переход зависит от текущего входного символа, как указывают метки на дугах графа переходов.

Рис. 4. 3.  Пример недетерминированного конечного автомата.

Переход выполняется всякий раз при чтении входного символа. Заметим, что переходы могут быть недетерминированными. На рис. 4.3 видно, что если автомат находится в состоянии S₁, и текущий входной символ равен  а,  то переход может осуществиться как в S₁, так и в  S₂.  Некоторые дуги помечены меткой пусто, обозначающей "пустой символ". Эти дуги соответствуют "спонтанным переходам" автомата. Такой переход называется спонтанным, потому что он выполняется без чтения входной цепочки. Наблюдатель, рассматривающий автомат как черный ящик, не сможет обнаружить, что произошел какой-либо переход.

Состояние S₃ обведено двойной линией, это означает, что S₃ - конечное состояние. Про автомат говорят, что он допускает входную цепочку, если в графе переходов существует путь, такой, что:

(1)        он начинается в начальном состоянии,

(2)        он оканчивается в конечном состоянии, и

(3)        метки дуг, образующих этот путь, соответствуют полной входной цепочке.

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

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

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

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

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