Долгов, Б. Ф. Мельников Самарский государственный университет Поступила в редакцию 25.03.2013 г. водится новое, простое доказательство того факта, что этот автомат совпадает, с точностью до переобозначения состояний, с универсальным автоматом Конвея. <...> Также приводятся несколько различных алгоритмов построения универсального автомата. <...> Ключевые слова: недетерминированные конечные автоматы, универсальный автоАннотация: в работе предлагаются алгоритмы построения автомата COM(L) и примат Конвея, алгоритмы построения. <...> Abstract: this work proposes algorithms of construction of automaton COM(L), it also contains new, simple prove of the fact that this automaton coincides, up to re-denoting states, with Conway’s universal automaton. <...> Several different algorithms of construction of universal automaton are also given. <...> В настоящей статье, также как и в [1], одновременно рассматриваются: • универсальный автомат Конвея; • совпадающий с ним (с точностью до переобозначения состояний) автомат COM(L); • само доказательство такого совпадения; • алгоритм построения автомата COM(L). <...> (Однако при этом подчеркнём, что формальная оценка сложности алгоритмов в рассматриваемый нами круг вопросов не входит. <...> «Каc нонический конечный автомат – это детерминированный автомат, имеющий минимально возможное число состояний». <...> Это – классическое определение, однако очевидно, что для описания на его основе практического алгоритма построения автомата необходимо много дополнительных вспомогательных действий. <...> № 2 173 В. Н. Долгов, Б. Ф. Мельников Итак, в данной работе мы рассматриваем недетерминированные конечные автоматы (НКА) и предлагаем приемлемые для практической реализации алгоритмы построения автомата COM(L). <...> Мы также приводим новое доказательство того факта, что этот автомат совпадает, с точностью до переобозначения состояний, с универсальным автоматом Конвея UL ([2] и др. <...> 2 Также в этом разделе мы доказываем, что ное отношение #, псевдоблок, блок, покрывающее подмножество блоков. <...> В разделе 3 мы повторяем определение автомата COM(L), формулировка определения них является <...>