ИСТИНА

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