On constructing minimal deterministic finite automaton recognizing a prefix-code of given cardinality.pdf В настоящее время префиксные коды находят широкое применение в различныхобластях информационных технологий. В связи с этим изучение их свойств представляетбольшой интерес.Наиболее естественный подход к распознаванию префиксных кодов основан на примененииконечных автоматов. Имеется ряд статей [1, 2], посвященных исследованиюзадачи минимизации числа состояний автомата, распознающего некоторый заданныйпрефиксный язык.В данной работе исследуется следующая задача: дано некоторое натуральное числоn, необходимо построить детерминированный конечный автомат, принимающийнекоторый префиксный код мощности и над алфавитом Е = {0,1} и имеющий наименьшеевозможное число состояний.Имеют место следующие свойства искомого автомата.Теорема 1. Пусть детерминированный конечный автомат A - минимальный автомат,принимающий некоторый непустой язык. Этот язык является префиксным тогдаи только тогда, когда в автомате A ровно одно терминальное состояние, причемвсе переходы из него ведут в тупиковое состояние.Теорема 2. Пусть детерминированный конечный автомат A - минимальный автомат,принимающий конечный префиксный язык. Тогда в этом автомате нет циклов,кроме петель, ведущих из тупикового состояния в само себя.Теорема 3. В детерминированном конечном автомате, принимающем некоторыйпрефиксный код заданной мощности n и имеющем минимальное число состояний, нетпереходов в тупиковое состояние, кроме как из единственного терминального и тупиковогосостояний.Так как искомый автомат не содержит циклов, можно выписать его состояния(кроме тупикового) в порядке обратной топологической сортировки:9o = f, 91, 92,... , 9fc-2 = s.Рассматривается соответствующая последовательность мощностей правых контекстовдля выписанных состояний:Oo, Й1, «2,. . . , «fc-2,где « = |Rqi | (Rqi -правый контекст состояния qi).Из равенств Rq0 = Rf = |е| следует, что a0 = 1. Так как состояния автомататопологически отсортированы и из каждого выходит два перехода в нетупиковые состояния,то все последующие элементы последовательности а являются суммой каких-либо двух предыдущих. Последний элемент a&-2 соответствует R s и равен мощностиязыка, принимаемого автоматом.Определение 1. Аддитивной цепочкой [3] называется последовательность элементовaj, такая, что1) ao = 1;2) aj = aj + ak для некоторых j, k < % при всех % > 0.Итак, искомому конечному автомату соответствует некоторая аддитивная цепочка.Из минимальной аддитивной цепочки посредством обратного построения можно получитьконечный автомат, принимающий некоторый префиксный код заданной мощности.Длина аддитивной цепочки на 2 меньше числа состояний в соответствующемавтомате. Отсюда вытекает следующая теорема.Теорема 4. Задача нахождения детерминированного конечного автомата с минимальнымчислом состояний, принимающего некоторый префиксный код заданноймощности n, эквивалентна задаче построения кратчайшей аддитивной цепочки, заканчивающейсячислом n.Из теоремы 4 следует дополнительное свойство искомого префиксного кода.Теорема 5. Префиксный код заданной мощности, соответствующий автоматус минимальным числом состояний, является полным.Задача о нахождении кратчайшей аддитивной цепочки является классической задачейдискретной математики [3]. Наиболее известным ее применением является задачаоб оптимальном алгоритме возведения произвольного числа в заданную степень,представляющая интерес для криптографии [4].Полиномиального решения данной задачи на данный момент неизвестно. Простыми достаточно эффективным приближенным решением является классический бинарныйметод возведения в степень [3]. Активно применяются методы поиска приближенногоответа, в том числе ведутся исследования по применению генетических алгоритмов[5] и «муравьиных алгоритмов» [6]. В работе [7] показано, что задача нахождениякратчайшей аддитивной цепочки, которая содержит в качестве подпоследовательностиданную последовательность bi , b2, ... , bk, является NP-полной. То есть естественноеобобщение рассматриваемой задачи не имеет полиномиального решения, если P = N P .

Скачать электронную версию публикации