Управляющие системы и машины, №3, 2016, статья 7
DOI: https://doi.org/10.15407/usim.2016.03.061
Чеботарев А. Н. О минимизации автоматов алгоритмом Хопкрофта. Управляющие системы и машины. 2016. № 3. C. 61-70.
УДК 519.713
А.Н. Чеботарев, д.т.н., Институт кибернетики имени В.М. Глушкова НАН Украины, просп. Глушкова, 40, Київ 03187, Україна
О минимизации автоматов алгоритмом Хопкрофта
Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном
понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве.
Загрузить полный текст PDF (на русском).
Ключовые слова: алгоритм Хопкрофта, минимизация автомата, разбиение, конгруэнция, временная сложность, дерево расщеплений.
Поступила 11.03.2016
