Недетерминированные конечные автоматы в разработке программного обеспечения?
Решение состоит в том, чтобы клонировать стиль вместо того, чтобы получить стиль, подобный этому:
HSSFCellStyle dataStyle = currentWorkbook.createCellStyle();
dataStyle.cloneStyleFrom(cell.getCellStyle());
dataStyle.setFont(font);
8 ответов
Механизмы наиболее регулярного выражения используют недетерминированные автоматы, так как они предлагают намного большую гибкость. DFAs намного более ограничиваются. Взгляните на некоторые реализации, и Вы будете видеть это. Microsoft даже подчеркивает этот факт в их документации класса Regex.NET:
Механизм регулярного выражения Платформы.NET является регулярным выражением отслеживания в обратном порядке matcher, который включает традиционный механизм Недетерминированного конечного автомата (NFA), такой как используемый Perl, Python, Emacs и Tcl.
Поведение при сравнении (первый абзац) – эта статья также предлагает объяснение для занятости NFA, а не более эффективного DFA.
Каюга использует недетерминированные конечные автоматы под капотом для сложной обработки событий. Ну, похоже, что они звонят, это "С сохранением информации Публикует/Подписывает для Контроля События", но я полагаю, что это - CEP.
Я полагаю, что некоторые их работы даже рассматривают, почему они используют модель автоматов. Вы могли бы хотеть ввести по абсолютному адресу вокруг их сайта.
... Автоматы каюги, расширенные от стандартных недетерминированных конечных автоматов.
Как Вы знаете, NFAs и DFAs в вычислительном отношении эквивалентны. Это - одна из первых теорем в теории автоматов. Существуют алгоритмы для преобразования того в другого (в отличие от Pushdown или машин Тьюринга).
Так. Почему один по другому? Поскольку представление данной проблемы с NFA намного легче, чем эквивалентный DFA.
править: с точки зрения фактического вычисления машины DFAs собираются пойти быстрее, потому что они не должны отслеживать в обратном порядке. Но они возьмут больше памяти для представления. (Мадам по сравнению с компромиссом ЦП)
Очень часто намного более легче создать NFA и затем работать с ним (единственная разница - то, что Вы держите ряд состояний вместо одного состояния). Если Вы хотите иметь его быстро, Вы можете сделать DFA, но не забываете, что время, чтобы сделать это экспоненциально (из-за результирующего автомата, может быть экспоненциально больше!).
С другой стороны, если Вы хотите сделать дополнительный язык, у Вас нет выбора, Вам нужен det. вариант.
Это - причина, почему отрицание не находится ни в одном из механизма регулярного выражения, только в классах ([^...]), где можно быть уверены, что автомат детерминирован.
viterbi алгоритм воздействует на скрытые марковские модели путем обработки их во многом как NFA. Не совсем идентичный, но конечно аналогичный.
Они полезны в приложениях как речь и распознавание текста.
I think the main reason for choosing a non-deterministic finite automaton would be to actually get the chosen match back. It's likely a lot harder to do it with a deterministic version.
If all you want to know is IF they match or not, and no other details, I would think compiling down to a finite automaton would be better.
Поправьте меня, если я ошибаюсь, но из своего класса компиляторов я помню, что иногда вы просто не можете использовать DFA, поскольку это привело бы к "взрыву" состояний.
Мой совет = взгляните на руководство для Адриана Терстонса Рагеля .
Существуют простые способы создания DFA напрямую, но я считаю, что они поддерживают только ограниченный круг операторов - в основном обычные подозреваемые EBNF. Рагель использует недетерминированные методы для составления сложных автоматов из более простых, а затем использует исключение и минимизацию эпсилона для создания эффективных детерминированных автоматов. Независимо от того, сколько странных операторов вам нужно, преобразование в минимальный детерминированный автомат всегда одно и то же, и каждая реализация оператора остается простой за счет использования недетерминированных методов.