Я думаю, вы в значительной степени прибили основные компромиссы в голове. NFA могут более эффективно использовать память, поскольку они могут кодировать O (2 n ) различных конфигураций в пространстве O (n), тогда как DFA для одного и того же языка может занимать экспоненциальное пространство. Вы также правы, что у NFA более медленные обновления; большинство алгоритмов для моделирования NFA требуют времени O (n) для вычисления переходов состояний (где n - число состояний) против времени O (1) для DFA.
Есть несколько других отличий между ними. Начнем с того, что DFA обычно легче кодировать, поскольку для каждой пары состояний и символов существует ровно один переход. Это естественным образом поддается многомерному массиву для таблицы переходов. В отличие от этого, NFA (или, что еще хуже, -NFA) обычно требует более сложного представления, поскольку для любого состояния может быть большое количество переходов. Однако NFA имеют то преимущество, что многие преобразования из сложных структур в автоматы проще с NFA. Например, каноническая конструкция совпадающего автомата из регулярного выражения генерирует & epsilon; -NFA, а не DFA, поскольку преобразование лучше всего выразить рекурсивным созданием меньших & epsilon; -NFA и последующим объединением их вместе с использованием движений-epsilon; , Можно напрямую преобразовать регулярное выражение в DFA, но сделать это значительно сложнее. Точно так же многие алгоритмы для генерации парсеров LR (k) могут быть более интуитивно мотивированы путем изучения того, как автомат распознавания дескрипторов работает с точки зрения NFA, а не с точки зрения DFA (хотя большинство алгоритмов генерации этих анализаторов идут непосредственно в DFA, а не в NFA). ).
Надеюсь, это поможет!