Многоаспектная минимизация недетерминированных конечных автоматов

недетерминированные конечные автоматы конечные автоматы базисные автоматы вершинная минимизация дуговая минимизация

Субиерархический метод решения задачи дифракции электромагнитной волны на теле, расположенном в свободном пространстве, О надежности схем, реализующих функции из P[3], ...

Б. Ф. Мельников, А. А. Мельникова МНОГОАСПЕКТНАЯ МИНИМИЗАЦИЯ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ (ЧАСТЬ 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. <...> А именно: в процессе выполнения процедуры канонизации автомата получены бинарное отношение # и множество блоков (разд. <...> Приведены два алгоритма объединения состояний недетерминированного автомата (разд. <...> 3 и 4); на их основе сформулированы сокращенный вариант алгоритма дуговой минимизации (разд. <...> При этом очевидно, что алгоритм дуговой минимизации, приведенный ниже, является более эффективным, чем алгоритм, приведенный ранее ([1]). <...> Как было отмечено в части I, его элементы можно рассматривать как состояния базисного автомата. <...> Но, кроме того, оно формирует множество так называемого псевдоблоков (псевдогридов); мы можем считать, что каждый из них – это некоторая пара (P,R), где P Qπ и R Qρ, причем такая, что для каждой пары состояний p P и r R выполнено условие p#r. <...> Если для некоторого псевдоблока (P, R) мы не можем расширить ни P, ни R для получения нового псевдоблока, то будем называть этот псевдоблок блоком (гридом). <...> Каждый из этих псевдоблоков соответствует состоянию некоторого конкретного автомата для заданного языка. <...> Более того, необходимым условием для определения данного языка конечным <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт