Мельникова Национальный исследовательский ядерный университет «МИФИ», филиал в г. Димитровграде Поступила в редакцию 8 февраля 2012 г. Аннотация: в статье рассматриваются свойства базисных конечных автоматов и функции разметки состояний произвольных недетерминированных конечных автоматов. <...> Некоторые из таких свойств описывают выходной язык любого состояния произвольного недетерминированного конечного автомата, определяющий заданный регулярный язык, через входные и выходные языки состояний эквивалентного канонического автомата. <...> В статье также доказаны некоторые свойства бинарного отношения, связывающего состояния двух канонических автоматов: для заданного языка и для зеркального к нему. <...> Ключевые слова: недетерминированный конечный автомат, базисный автомат, функции разметки состояний, таблица соответствия состояний. <...> Abstract: we consider in this paper properties of basis fi nite automata and state-marking functions. <...> Some such properties write the output language of any state of any automaton defi ning the given regular language using input and output languages of states of equivalent canonical automaton. <...> We also prove some properties of the binary relation defi ned on the sets of states of two canonical automata: for the given language and for its mirror image. <...> Key words: nondeterministic fi nite automaton, basis automaton, state-marking functions, table of state correspondence. <...> Для недетерминированного конечного автомата Рабина—Скотта KQ S F S d S =( , , , , ), (1) (мы допускаем возможность e -переходов, т.е. функция переходов d является функцией вида de ниже будем также обозначать язык автомата (1) (т.е. L() определяемый им язык записью L() K ) буквой L. соответственно входной и выходной языки состояния q — т.е. языки, определяемые автоматами Через LK in () и LK out q (, , , ,{ })QS q S d соответственно. <...> Для эквивалентного автомату (1) канонического автомата* * Во всех предыдущих публикациях канонический автомат рассматривается без возможного «дохлого состояния» («dead state» в английских текстах <...>