Laboratory of Mathematical Logic

Пятница, 5 апреля, комната 106. Начало в 18:00.

Докладчик: Ю. Лифшиц.

СВЯЗЬ КОНЕЧНЫХ АВТОМАТОВ С РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ ЗАДАЧА ОБ УНИВЕРСАЛЬНОМ ГРАФЕ

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

Количество переходов в конечном недетерминированном автомате без пустых переходов, который распознает регулярный язык из

букв -- не меньше, чем количество ребер в Универсальном графе (УГ).

В той же статье получена и верхняя оценка:

Для любого регулярного выражения, построенного за

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

переходов.

Таким образом, цель настоящей работы -- получить нижнюю оценку на количество ребер в УГ. Оценка, полученная в работе Hagenah и Muscholl --

. Результат настоящей работы -- нижняя оценка

. Основная идея доказательства -- переход от ориентированного графа к стрелочным структурам. Однако, по мнению автора, таким путем невозможно получить оценку

.