Б. Ф. Мельников, А. А. Мельникова
МНОГОАСПЕКТНАЯ МИНИМИЗАЦИЯ
НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ
(ЧАСТЬ I. <...> В первой части настоящей статьи рассматриваются некоторые
вспомогательные алгоритмы, необходимые одновременно для двух проблем
минимизации недетерминированных конечных автоматов – вершинной и дуговой. <...> Приводится несложный алгоритм минимизации детерминированных
автоматов, с помощью которого производится одновременное построение
функций разметки состояний. <...> Доказываются вспомогательные утверждения о
входных языках состояний базисного автомата, необходимые для алгоритмов
эквивалентного преобразования произвольных недетерминированных конечных автоматов. <...> Ключевые слова: недетерминированный конечный автомат, базисный автомат,
алгоритмы эквивалентного преобразования, вершинная минимизация, дуговая
минимизация. <...> In the first part of the article, the authors consider some auxiliary algorithms for two problems of minimization of nondeterministic finite automata: vertex-minimization and edge-minimization. <...> The article proves some auxiliary propositions
about input languages of the basis automaton states, necessary for algorithms of
equivalent transformation of nondeterministic finite automata. <...> Key words: nondeterministic finite automaton, basis automaton, algorithms of
equivalent transformation, state-minimization, edge-minimization. <...> Введение
В первой части данной статьи рассматриваются вопросы, связанные
с проблемой минимизации недетерминированных конечных автоматов, причем как по числу вершин, так и по числу дуг. <...> Приводятся вспомогательные
утверждения и алгоритмы, нужные для решения этих задач, причем необходимые как для точного решения, так и для описания приближенных алгоритмов реального времени (anytime-алгоритмов). <...> В разделе 1 приводятся применяемые
обозначения – они согласованы с использовавшимися в предыдущих работах
авторов ([1–5] и др. <...> ). В разделе 2 приводится несложный алгоритм минимизации детерминированных автоматов, с его помощью производится одновременное построение функций разметки состояний. <...> В разделе 3 доказываются
вспомогательные утверждения о входных языках состояний базисного автомата <...>