Характеристики производительности неминимального DFA

Что касается вашего первого вопроса о времени выполнения неоптимального DFA. Чисто теоретически ваша интуиция о том, что он все еще должен работать за O (n), верна. Однако представьте (в качестве примера) следующий псевдокод для оператора Kleene-Star:

// given that the kleene-star operator starts at i=something
while string[i] == 'r':
    accepting = true;
    i++;
while string[i] == 'r':
    accepting = true;
    i++;
// here the testing of the input string can continue for i+1

Как видите, первые два цикла while идентичны и могут рассматриваться как избыточное состояние. Однако «разделение» циклов while снизит (среди прочего) точность прогнозирования ветвлений и, следовательно, общее время выполнения (см. блестящее объяснение прогнозирования ветвлений Mysticial для получения более подробной информации здесь.

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

Что касается вашего второго вопроса - здесь я не уверен, что вы имеете в виду. В конце концов, если вы сделаете преобразование правильно, вы должны получить довольно оптимальный DFA.

РЕДАКТИРОВАТЬ: В ходе обсуждения возникла идея, что может быть несколько неминимальных DFA, построенных из одного NFA, которые будут иметь разную эффективность (в любой выбранной мере), а не в реализации, а в структуре DFA. Это невозможно, так как существует только один оптимальный DFA. Вот набросок доказательства этого:

1. Предполагая, что наша процедура создания и минимизации DFA оптимальна.
2. при применении процедуры мы начнем сначала с построения DFA. На этом шаге мы можем создать бесконечно много эквивалентных состояний. Все эти состояния каким-то образом связаны с графом NFA.
3. На следующем шаге мы исключаем все недостижимые состояния. Это безразлично к производительности, поскольку недостижимое состояние будет соответствовать «мертвому коду» — никогда не выполняться.
4. На четвертом шаге мы минимизируем DFA, группируя эквивалентные состояния. Вот тут-то и становится интересно — идея в том, что мы можем делать это разными способами, что приводит к разным DFA с разной производительностью. Однако единственный «выбор», который у нас есть, — это назначить состояние другой группе. Итак, ради аргументов, мы предполагаем, что можем это сделать. Но по идее алгоритма минимизации мы можем сгруппировать только эквивалентные состояния. Таким образом, если у нас есть разные варианты группировки определенного состояния, в силу транзитивности эквивалентности не только состояние будет эквивалентно обеим группам, но и группы будут эквивалентны. Таким образом, если бы мы могли группировать по-другому, алгоритм не был бы оптимальным, поскольку он сгруппировал бы все состояния в группах в первую очередь в одну группу. Следовательно, предположение о том, что могут быть разные минимизации, должно быть неверным.

Рассуждение о том, что «время выполнения» для принятия ввода будет таким же, поскольку обычно потребляется один символ ввода; Я никогда не слышал о понятии «время выполнения» (в смысле асимптотической сложности времени выполнения) в контексте DFA. Минимизация направлена ​​на минимизацию количества состояний (т. е. на оптимизацию «размера реализации») DFA.