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

    Глава 1. Основные понятия и определения из
      теории недетерминированных автоматов
                1.1. Определение и понятия
              недетерминированного автомата
      Недетерминированные автоматы являются общим случаем конечных
детерминированных цифровых автоматов, основные понятия и определения
которых рассмотрены во многих источниках, в том числе и в 1, 2.
      Под НДА понимается математическая модель устройства переработки
цифровой (дискретной) информации, для которой не выполняются условия
однозначности функций переходов. Кроме того, для НДА, как и для
детерминированного конечного цифрового автомата, могут не соблюдаться
также и условия полноты переходов. Термин «недетерминированный», как
было отмечено в 3, наводит на мысль как о чем-то случайном, однако в
НДА ничего случайного нет. В данном случае под НДА понимается просто
формализм для определения (распознавания) множества цепочек (слов), а
слово «автомат» в названии НДА присутствует потому, что формализм
является обобщением формализма, используемого для определения обычного
детерминированного конечного автомата. Таким образом, НДА не следует
смешивать с вероятностным автоматом, в котором переходы осуществляются
в любое из состояний с некоторой вероятностью.
      Понятие НДА было впервые введено в работах американских ученых
М.О.Рабина и Д. Скотта 4. В дальнейшем понятие НДА успешно
использовалось в работах, связанных с решением теоретических вопросов
информатики, например, в 5,6,7. Однако в этих работах НДА
рассматривались в основном с точки зрения использования такой
математической модели для построения различных распознавателей и
компиляторов. В частности, в работах 5, 8] НДА были представлены под
названием «источники». При этом под источником понимается
ориентированный граф, однозначно определяющий событие S в некотором
алфавите Z, порождаемое множеством всех путей из начальных вершин в
заключительные.
      В работах [9 и [10] НДА был представлен системой предикатных
формул на языке исчисления предикатов 1-го порядка, а также системой
бескванторных предикатных формул, формализующих все реализуемые
частные события алгоритма функционирования цифрового автомата,
полученных после спуска кванторов.
      В дальнейших работах автора 2,11] модель НДА, представленная в
виде стандартной и универсальной системы рекуррентных бескванторных
предикатных формул, названная системой канонических уравнений
недетерминированного автомата (НД СКУ), стала основой для синтеза
систем логического управления процессами и объектами.

                                                                     7