Home

Семинар 5 апреля 2002 года

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

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

СВЯЗЬ КОНЕЧНЫХ АВТОМАТОВ С РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ ЗАДАЧА ОБ УНИВЕРСАЛЬНОМ ГРАФЕ
Эта задача возникла в теории конечных автоматов. Известно, что для языка каждого регулярного выражения существует конечный автомат, который этот язык распознает. При попытке дать нижнюю оценку количества переходов в этом автомате Hagenah и Muscholl сформулировали следущий результат:
Количество переходов в конечном недетерминированном автомате без пустых переходов, который распознает регулярный язык из $ n $ букв -- не меньше, чем количество ребер в Универсальном графе (УГ).
В той же статье получена и верхняя оценка:
Для любого регулярного выражения, построенного за $ n $ шагов, можно построить недетерминированный конечный автомат без пустых переходов, который будет распознавать язык этого выражения и содержать не более чем $ С n log^2 n $ переходов.
Таким образом, цель настоящей работы -- получить нижнюю оценку на количество ребер в УГ. Оценка, полученная в работе Hagenah и Muscholl -- $ c n log n $. Результат настоящей работы -- нижняя оценка $ c_1 n log^2 n/log log n $. Основная идея доказательства -- переход от ориентированного графа к стрелочным структурам. Однако, по мнению автора, таким путем невозможно получить оценку $ c_2 n log^2 n $.