Многоаспектная минимизация недетерминированных конечных автоматов (Часть I. Вспомогательные факты и алгоритмы)

В первой части настоящей статьи рассматриваются некоторые вспомогательные алгоритмы, необходимые одновременно для двух проблем минимизации недетерминированных конечных автоматов - вершинной и дуговой. Приводится несложный алгоритм минимизации детерминированных автоматов, с помощью которого производится одновременное построение функций разметки состояний. Доказываются вспомогательные утверждения о входных языках состояний базисного автомата, необходимые для алгоритмов эквивалентного преобразования произвольных недетерминированных конечных автоматов.