Главная > Энциклопедия кибернетики. Т.1
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

1
Оглавление
email@scask.ru