МАТЕМАТИЧЕСКИЕ МЕТОДЫ СИСТЕМНОГО АНАЛИЗА И УПРАВЛЕНИЯ УДК 519.688 МУЛЬТИЭВРИСТИЧЕСКИЙ ПОДХОД К ПРОБЛЕМЕ ЗВЕЗДНО-ВЫСОТНОЙ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ С. В. <...> Баумгертнер, Б. Ф. Мельников Тольяттинский государственный университет Поступила в редакцию 06.04.2010 г. Аннотация. <...> В данной статье рассматривается задача построения регулярного выражения, оптимального с точки зрения звездной высоты, для заданного конечного автомата. <...> Предлагается anytime-алгоритм, позволяющий получить псевдо-оптимальное решение за определенный промежуток времени. <...> Ключевые слова: Проблема звездное высоты, недетерминированный конечный автомат, регулярное выражение, незавершённый метод ветвей и границ, мультиэвристический подход. <...> In this paper, we consider the problem of searching regular expression with minimum star height by finite automata. <...> ВВЕДЕНИЕ В теории формальных языков звёздной высотой регулярного выражения называется мера сложности, которая равна максимальной глубине вложенности операции *. <...> Пусть r и s — произвольные регулярные выражения. <...> Звёздной высотой регулярного языка называется минимальная из звёздных высот регулярных выражений, определяющих этот язык. <...> Несмотря на то, что звёздную высоту регулярного выражения вычислить достаточно просто, вычисление звёздной высоты регулярного языка обычно представляет собой очень сложную проблему. <...> Однако легко заметить, что данный язык является множеством всех слов над алфавитом A, заканчивающихся на a. <...> Следовательно, данный язык может быть представлен другим регулярным выражением, (a + b)*a, звёздная высота которого равна 1. <...> Проблема звёздной высоты — одна из важных задач в теории формальных языков. <...> Она оставалась нерешённой в течение примерно 25 лет, пока Хашигучи в 1988 не опубликовал алгоритм поиска звёздной высоты для любого регулярного языка [5]. <...> Однако алгоритм был совершенно неприменим на практике. <...> Процедура, описанная Хашигучи, ведёт к вычислениям, которые невозможны даже для маленьких примеров <...>