УДК 519.178 ОБ ОДНОМ АЛГОРИТМЕ ПОСТРОЕНИЯ УНИВЕРСАЛЬНОГО АВТОМАТА КОНВЕЯ М. А. <...> Зубова, Б. Ф. Мельников Тольятинский государственный университет Поступила в редакцию 8.02.2012 г. Аннотация. <...> В статье получено доказательство совпадения универсального автомата Конвея и автомата COM, определяющегося через множество всевозможных дуг всех автоматов для заданного регулярного языка. <...> Следствием этого доказательства является возможность замены алгоритма построения универсального автомата на алгоритм построения автомата COM. <...> In this article, the proof of equality of the universal automaton and automaton COM was received, where automaton COM is defi ned by the set of the possible edges of the regular language. <...> A consequence of this is the possibility of replacing the algorithm for constructing the universal automaton on the algorithm for constructing automaton COM. <...> Conway’s universal automaton; the set of possible edges. <...> ВВЕДЕНИЕ Каждому языку L можно поставить в соответствие минимальный детерминированный автомат. <...> Такой автомат конечен в том и только том случае, когда L является регулярным языком. <...> Кроме того, для любого автомата, распознающего язык L, существует гомоморфизм этого автомата на минимальный детерминированный автомат. <...> * Ещё одним возможным автоматом-эквивалентом (автоматом-инвариантом) языка L является так называемый универсальный автомат, о нём и пойдёт речь в данной статье. <...> Универсальный автомат впервые был определён английским математиком и создателем клеточного автомата «Игра “Жизнь”» Дж. <...> Конвеем в [1], где был использован для поиска наилучшего приближения семейства заданных регулярных языков к языку L. <...> При исследовании недетерминированных автоматов, задающих язык L, универсальный автомат имеет такую же важность, какую имеет минимальный детерминированный автомат в отношении детерминированных автоматов для этого же языка. <...> Как и в случае с минимальным детерминированным автоматом, универсальный автомат конечен тогда и только тогда, когда L регулярен. <...> К тому же, универсальный автомат обладает другими полезными свойствами — например: всякий задающий язык L минимальный <...>