Введение в архитектуру компьютеров


Язык диспозиций


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

Будем задавать диспозицию D знаковой системой S, множеством операторов M = {A1, A2, ..., An} (в дальнейшем оно предполагается конечным) и графом диспозиции Г(D). Каждый оператор Ai имеет один вход и Pi выходов (S1, S2, ... , SРi). Оператор Ai осуществляет некоторое преобразование Ai текстов в знаковой системе S и проверяет серию условий w0i, w1i, ... , wki. Когда оператор Ai применяется к тексту T, он проверяет, удовлетворяет ли текст T серии условий

w0i, w1i, ... , wki, и преобразует текст T по правилу Ai в текст T¢. Особую роль играет условие w0i, которое будем называть условием применимости оператора Ai. Если оно выполняется (w0i = 1), то оператор работает, как было описано выше. Иначе (т. е. если w0i = 0) оператор Ai оставляет текст неизменным (т. е. T¢ = T). Для каждого оператора Ai задается Pi функций:

j1i (w0i, w1i, ... , wki);

j2i (w0i, w1i, ... , wki);

. . .

jРii (w0i, w1i, ... , wki).

Каждая из этих функций может принимать два значения: 1 (возможно) и 0 (невозможно). Будем называть систему функций правильной, если для каждой функции существует, по крайней мере, один набор значений аргументов, при котором она принимает значение 1.

Графом диспозиции Г(D) будем называть связный граф, вершинам которого сопоставлены либо операторы диспозиции D, либо знак #. Вершины обладают следующими свойствами:

· имеется только одна вершина, называемая входом диспозиции, и обозначается aвх;




- Начало -  - Назад -  - Вперед -