Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 8 стр.

        Использование понятий НДА как математической модели в виде НД
СКУ, как будет показано ниже, является эффективным средством для
формализации описания сложных алгоритмических процессов управления, в
том числе алгоритмов управления с параллельными взаимодействующими
ветвями. Используя различные эквивалентные преобразования такого
описания, можно построить различные структуры устройств управления для
систем       параллельной   обработки,         позволяющие    увеличить    их
производительность и уменьшить аппаратурные затраты.
        Наиболее простое определение НДА основывается на языке графов.
НДА называется произвольная диаграмма В над входным алфавитом, в
которой выделены множества начальных и финальных вершин. Под
диаграммой В понимается направленный граф, вершины которого помечены
буквами из алфавита В = [b0, b1, ..., bm (или цифрами). Каждая вершина графа
отмечена соответствующими выходными сигналами из абстрактного
выходного алфавита W=w0, w1, ..., wy или совокупностью выходных
двоичных элементарных сигналов из структурного алфавита Y=y1, y2, ..., yN.
Ребра графа помечены буквами из абстрактного входного алфавита Z = z0,
z1, ..., zF или частными входными сигналами, являющихся сочетаниями
двоичных элементарных сигналов из структурного алфавита Х =x1, x2, ..., xL].
      Понятие «произвольный» здесь означает, что граф может не
удовлетворять условиям автоматности 5. В частности, допускаются
следующие особенности:
      а) из некоторой вершины могут выходить несколько ребер,
помеченных одной и той же буквой входного алфавита Z или одним и тем
же частным входным сигналом из алфавита [X] (нарушение однозначности);
      б) из ряда вершин может вообще не выходить ни одно ребро,
помеченное некоторой буквой входного алфавита (нарушение полной
определенности);
      в) имеется несколько начальных вершин.
      Автоматная интерпретация НДА предполагает следующее его
функционирование. Если в некоторый момент времени (t) возбуждена
вершина с номером i(bi) и имеет место входной сигнал zk, то в момент
времени (t+1) будут возбуждены все вершины, в которые ведут ребра с
пометкой zk . Если таких ребер нет, то не будет возбуждена ни одна вершина.
     Так как в каждый момент времени (t) может быть возбуждено
несколько вершин, то для определения вершин, которые будут возбуждены в
момент времени (t +1), необходимо объединить множество вершин,
возбуждаемых из каждой возбужденной вершины. В момент времени t=0
возбуждены все начальные вершины.
     В каждом такте будут выдаваться выходные сигналы, которыми были
отмечены одновременно возбужденные вершины.

                                                                            8