АВТОМАТ НЕДЕТЕРМИНИРОВАННЫЙ

— автомат, который при данном входном символе и внутреннем состоянии может переходить в несколько различных внутренних состояний. Формально А. н. - это пятерка такая, что отображение не является однозначным. По аналогии с теорией автоматов детерминированных можно ввести понятия представления (порождения) множеств для А. н. Если два автомата конечных, представляющие одно и то же мн-во, считать эквивалентными, то существует алгоритм, позволяющий по каждому конечному А. н. построить эквивалентный ему конечный детерминированный автомат. При этом, естественно, детерминированный автомат имеет большее число состояний, чем А. н. В общем случае для любых автоматов подобное утверждение неверно. Напр., класс множеств, порождаемых недетерминированными автоматами с магазинной памятью, шире, чем класс множеств, порождаемых такими же детерминированными автоматами.

Лит.: Пупанов О. Б. О сравнении двух типов конечных источников. В кн.: Проблемы кибернетики, в. 9. М., 1963; Пюбич Ю. И. Оценки числа состояний, возникающих при детерминизации недетерминированного автономного автомата «Доклады АН СССР», 1964, т. 155, 1. М. И. Кратко.