Можно ли недетерминированные конечные автоматы (NDFA) эффективно преобразовать в детерминированные конечные автоматы (DFA) в субэкспоненциальном пространстве / времени?

Двадцать лет назад я создал пакет регулярных выражений, который включал преобразования из регулярных выражений в конечный автомат (DFA) и поддерживал множество закрытых операций с регулярными выражениями (звезда Клина, конкатенация, обратное, операции над множествами и т. Д.). Я не был уверен в худшем случае производительности моего пакета.

DFA обладает той же выразительной силой, что и NDFA, поскольку NDFA в n-состоянии можно легко преобразовать в DFA, имеющий 2 ^ n состояний. Однако существуют ли какие-либо нижние ограничения верхней границы для такого преобразования, которые не требуют экспоненциального взрыва в состоянии?

Я не смог придумать примеры некорректных регулярных выражений или NDFA, но я не тратил много времени на размышления об этом. Я предполагаю, что регулярное выражение типа ((((e | A | B | C) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) *, который смешивает много чередований, и у звезд Клини будет NDFA линейного размера, но обширный DFA.

Известно, что для каждой пары натуральных чисел, n,aтаких n <= a <= 2^n, что существует минимальный NDFA с nсостояниями, у которых соответствующий эквивалентный минимальный dfa имеет aсостояния (более четырехбуквенного алфавита).

См. Статью здесь: Детерминированные взрывы минимальных недетерминированных конечных автоматов над фиксированным алфавитом .

Автореферат статьи:

Мы показываем, что для всех целых чисел n и α, таких что n ≤ α ≤ 2 ^ n, существует минимальный недетерминированный конечный автомат из n состояний с четырехбуквенным входным алфавитом, эквивалентный минимальному детерминированному конечному автомату которого точно соответствует состоянию. Отсюда следует, что в случае четырехбуквенного алфавита не существует «магических чисел», то есть дыр в иерархии. Это улучшает аналогичный результат, полученный Geffert для растущего алфавита размера n + 2 (Proc. 7th DCFS, Como, Italy, 23-37).

Итак, я полагаю, что ответ на ваш вопрос - нет.

Классическим примером языка с экспоненциальным разделением между размером DFA и размером NFA является следующий конечный язык: двоичные строки длиной ровно 2n, в которых первая половина не равна второй половине. НФА будет угадывать индекс я, в котором первая и вторая половина не согласны. Нижняя граница для DFA следует, например, из сложности связи.

Минимальный DFA, соответствующий NFA, имеет 2 ^ n состояний в худшем случае, поэтому вы не можете ничего гарантировать. Не имея конструктивного примера, причина в том, что в NFA вы можете находиться в любом произвольном подмножестве состояний после чтения определенной входной строки, и каждое такое подмножество может вести себя по-разному, наблюдая за одним символом. Предположим, что язык с двумя символами в алфавите (a и b) и NFA N с n состояниями, который начинается с принимающего состояния в s_0. Теперь перечислим все подмножества состояний N и создадим таблицу переходов таким образом, чтобы наблюдение «a» из подмножества S_i привело вас к подмножеству S_i + 1, а наблюдение b - к подмножеству S_i-1 (я думаю, это выполнимо для некоторых перечислений ). Теперь этот автомат имеет n состояний и принимает такие последовательности ma и nb, что mn = 0 mod 2 ^ | N |, и не может быть выражено с DFA, который имеет менее 2 ^ | N | состояния (поскольку может потребоваться циклически проходить через все подмножества состояний NFA N).