Все мои учебники используют один и тот же алгоритм для создания DFA с заданным регулярным выражением: во-первых, создайте NFA, который распознает язык регулярных выражений, затем, используя конструкцию подмножества (он же «powerset»), преобразуйте NFA в эквивалентный DFA ( при желании минимизировать DFA). Я также однажды услышал от профессора намеки на существование других алгоритмов. Кто-нибудь знает что-нибудь? Возможно тот, который идет непосредственно от регулярного выражения в DFA без промежуточного NFA?
automata-theory
regular-expressions
dfa
BlueBomber
источник
источник
Ответы:
Существуют разные алгоритмы для преобразования регулярных выражений в конечные автоматы. Вы можете перейти непосредственно от регулярных выражений к DFA, не создавая сначала никакого другого автомата, неявно выполняя конструкцию подмножества при генерации автомата. Другим вариантом прямого получения детерминированных автоматов является использование метода производных.
Проверка того, представляет ли регулярное выражение язык, содержащий все строки, является полной проблемой PSPACE (см. Этот ответ для справки). Проверка того, что DFA принимает этот язык, может быть выполнена за полиномиальное время, поэтому, если вы перейдете непосредственно от регулярного выражения к DFA, где-то произойдет взрыв.
Я понимаю литературу, что мы можем выбрать переводы, которые позволят нам локализовать взрыв. Это означает, что существуют разные способы перехода от регулярного выражения к конечному автомату, и предпочтительны линейные или полиномиальные методы. Обычно экспоненциальные издержки подталкиваются к определению автоматов.
Была проделана большая работа по выявлению подсемей регулярных выражений, из которых мы можем эффективно генерировать DFA. Это направление работы зависит от используемого вами перевода. Это означает, что вы исправляете отображение регулярных выражений в NFA и пытаетесь охарактеризовать регулярные выражения, которые отображаются в DFA.
Стандартная конструкция автоматов из регулярных выражений не является предпочтительной конструкцией в такой работе. Выбранные конструкции создают автоматы, которые очень похожи на структуру регулярного выражения. В этих конструкциях используется понятие производной регулярного выражения.
Если вы думаете о состоянии автомата как о представлении всех строк, принятых из этого состояния, (частичные) производные позволяют вам рассматривать регулярные выражения как состояния . Контраст со стандартной конструкцией учебника, которая интуитивно рассматривает регулярные выражения как автоматы, а не состояния.
Соответствие между регулярными выражениями и состояниями автомата и детерминизма явно обсуждается Берри и Сетхи, которые объединяют понятие производных Бжозовского с идеей различения вхождений одного и того же символа, чтобы дать основанный на синтаксисе перевод регулярных выражений в конечные автоматы.
Эта статья основана на более ранней работе Брюггеманна-Кляйна и изучает случаи, в которых вы можете использовать производные для генерации DFA за полиномиальное время. После этой работы проделана большая работа. Это было важно с точки зрения веб-технологий, потому что регулярные выражения, которыми можно эффективно управлять (иначе говоря, соответствующие DFA), были важны для обработки SGML и XML.
Было много работы по изучению других частных случаев детерминированных регулярных выражений. Самая недавняя статья, в которой изучается, когда некоторые из этих проблем могут быть решены за линейное время, относится к 2012 году.
источник