Б. Ф. Мельников, А. А. Мельникова
МНОГОАСПЕКТНАЯ МИНИМИЗАЦИЯ
НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ
(ЧАСТЬ II. <...> Во второй части статьи подробно рассматривается пример построения бинарного отношения # и множества блоков заданного регулярного
языка – в процессе выполнения процедуры канонизации задающего его автомата. <...> Приведены два алгоритма объединения состояний недетерминированного автомата. <...> На основе этих алгоритмов сформулированы сокращенный вариант алгоритма дуговой минимизации, а также алгоритм добавления дуги. <...> Ключевые слова: недетерминированный конечный автомат, базисный автомат,
алгоритмы эквивалентного преобразования, вершинная минимизация, дуговая
минимизация. <...> In the second part of this paper the authors consider the detailed example
of construction of binary relation # and the set of grids of the given regular language; this construction is made in the process of canonization of an automaton defining this language. <...> The article considers two algorithms of combining states of
nondeterministic automaton. <...> Based on these algorithms, the researchers formulate a
brief algorithm of the edge-minimization, and also an algorithm for adding an edge. <...> Key words: nondeterministic finite automaton, basis automaton, algorithms of
equivalent transformation, state-minimization, edge-minimization. <...> А именно: в процессе выполнения процедуры канонизации автомата получены бинарное отношение # и множество
блоков (разд. <...> Приведены два алгоритма объединения состояний недетерминированного автомата (разд. <...> 3 и 4); на их основе сформулированы сокращенный вариант алгоритма дуговой минимизации (разд. <...> Приведенный в статье алгоритм решения проблемы дуговой минимизации является упрощением двух алгоритмов, опубликованных авторами ранее. <...> При этом очевидно, что алгоритм дуговой минимизации, приведенный ниже, является более эффективным, чем алгоритм, приведенный ранее
([1]). <...> Мы продолжим нумерацию формул, рисунков и таблиц,
начатую в первой части, – однако для разделов и библиографических ссылок
нумерация здесь начинается заново. <...> Как было отмечено в части I, его элементы можно рассматривать как состояния базисного
автомата <...>