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

вполне определенное состояние автомата и определяются переходы между
этими состояниями. НДА является более компактным представлением
автомата, поскольку при детерминизации НДА с т реализуемыми в нем
событиями (состояниями) эквивалентный ему детерминированный автомат
может иметь не более М  2m состояний, что будет доказано в дальнейшем. С
другой стороны, можно утверждать, что детерминированный автомат с М
состояниями может быть представлен НДА с ]log2 М[ состояниями.
Получение такого НДА возможно, например, путем кодирования
детерминированного автомата состояниями НДА. Отсюда следует, что
операция детерминизации над НДА и операция кодирования эквивалентного
ему детерминированного автомата являются операциями обратными друг
другу.
      В том случае , когда в графе автомата выделено единственное
начальное состояние (событие) и при любых входных последовательностях
сигналов никогда не будут одновременно возбуждены две и более вершин
(или одновременно существовать два или более события), такой автомат
будет являться детерминированным. В этом случае каждой вершине графа
или событию, реализуемому в автомате, будет соответствовать свое вполне
определенное состояние автомата.
      Над НДА возможно выполнение большого количества операций, из
которых, кроме отмеченных выше операций детерминизации и кодирования,
можно выделить: операцию стягивания начальных и финальных вершин,
которые отмечены одним и тем же выходным сигналом; операции
минимизации, отрицания, конкатенации, суммирования, объединения и др.
Указанные операции над НДА рассматриваются как операции над СКУ,
описывающими поведение НДА. Они используются для преобразования СКУ
с целью построения структуры автомата, удовлетворяющей определенным
требованиям. Это оказалось возможным благодаря использованию модели
НДА в виде СКУ, представляющую собой простую стандартную и
универсальную систему рекуррентных бескванторных предикатных формул,
правая часть которых представляет собой ДНФ булевых функций.

        1.2. Общие сведения о выборе языков для
     представления недетерминированных автоматов
      НДА, также как и конечные цифровые автоматы, используются в
качестве математической модели для формального описания алгоритмов
логического управления в системах обработки дискретной информации. При
этом наиболее эффективно они могут быть использованы в системах,
реализующих параллельную обработку информации. Для формального
описания таких математических моделей используются языки двух типов:
начальные и стандартные, которые отличаются друг от друга способом
задания функций переходов.

                                                                       10