DOI: 10.17587/prin.13.449-461

УДК: 004, 004.3, 004.9, 519.6, 519.7, 519.8

Структурная модификация конечного автомата для решения проблемы экспоненциального взрыва

А. Бернадотт , канд. мед. наук, доц., bernadotte.alexandra@intsys.msu.ru, Национальный исследовательский технологический университет "МИСиС", ООО "Нейроспутник", Москва, Механико-математический факультет МГУ им. М. В. Ломоносова

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

Ключевые слова: конечный автомат, экспоненциальный взрыв, сетевые системы обнаружения вторжения, структурная сложность, понижение сложности, регулярные языки, регулярные выражения

Стр. 449—461