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


Язык диспозиций - часть 3


Если этой вершине сопоставлен знак #, то процесс на этом заканчивается, и образовавшийся к этому моменту текст считается результатом диспозиции.

Одному и тому же начальному тексту может соответствовать несколько результатов (если один, то диспозиция однозначна).

Диспозиция называется алгоритмической, если для любого начального текста на каждом шаге возможен (а следовательно, и предписан) переход только к одной вершине графа Г(D).

Заметим, что алгоритмическая диспозиция еще не обязательно есть алгоритм, так как сами преобразования могут быть определены неоднозначно (например, марковские подстановки без указания на то, какое вхождение слова берется). Мы уже использовали понятие “реализация диспозиции”, описывая, как диспозиция преобразует исходный текст. Определим реализацию диспозиции D формально.

Будем рассматривать в графе Г(D) пути (называемые сквозными), состоящие из последовательности вершин:

al0 = aвх, al1, ..., aln, aln+1 = aвыхj,

так как ali ® 

 (кроме aвых1, ..., aвыхn), то каждому сквозному пути будет сопоставлена сквозная последовательность операторов
,
, ... ,
. Пусть оператор
(сопоставленный вершине al1) применен к тексту T0, а каждый оператор
 преобразует текст Ti-1 в текст Ti. Тогда если в сквозной последовательности операторов после применения каждого оператора
 (кроме
) к тексту Ti-1 возможно применение
 к тексту Ti, то данную сквозную последовательность операторов и соответствующую ей последовательность текстов T0, T1, ..., Tn будем называть реализацией диспозиции D, а текст Tn – результатом применения диспозиции к тексту T0. Этот факт будем записывать так:

.

Знак ® означает: поставлен в соответствие.

Иногда удобнее описывать метод решения ряда задач как диспозицию, а затем уже тем или иным способом переходить к алгоритмам решения этих задач. Чтобы выделить алгоритмические диспозиции, следует рассматривать только такие наборы M операторов, что для " Ai Î M не более чем одна из функций j1i, j2i, ..., jрii принимает значение 1 вне зависимости от набора значений аргументов.




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



Книжный магазин