Какие существуют алгоритмы для построения DFA, который распознает язык, описанный данным регулярным выражением?

11

Все мои учебники используют один и тот же алгоритм для создания DFA с заданным регулярным выражением: во-первых, создайте NFA, который распознает язык регулярных выражений, затем, используя конструкцию подмножества (он же «powerset»), преобразуйте NFA в эквивалентный DFA ( при желании минимизировать DFA). Я также однажды услышал от профессора намеки на существование других алгоритмов. Кто-нибудь знает что-нибудь? Возможно тот, который идет непосредственно от регулярного выражения в DFA без промежуточного NFA?

BlueBomber
источник
Добро пожаловать на cstheory, сайт вопросов и ответов по исследовательским вопросам теоретической информатики (TCS). Ваш вопрос не является вопросом исследовательского уровня в TCS. Пожалуйста, смотрите FAQ для получения дополнительной информации о том, что подразумевается под этим. Ваш вопрос может быть пригодным для вычислительной техники , которая имеет более широкую сферу применения.
Каве
1
почему вы всегда используете этот шаблон комментария? Видимо, есть как минимум 5, кто не согласен с вами. Я хотел бы предложить вам дать такие вопросы шанс.
AJed
@JJed, я не всегда использую этот комментарий. Я использую его, когда вопрос кажется мне не по теме, но может подойти для информатики . Голосование вверх не означает, что вопрос является тематическим, и этот вопрос не кажется мне вопросом исследовательского уровня, поэтому я думаю, что комментарий уместен. (Тот факт, что кто-то может написать ответ исследовательского уровня на вопрос, не делает вопрос исследовательским уровнем.) PS: Я думаю, что эта дискуссия больше подходит для теоретической метаинформатики .
Каве

Ответы:

13

Существуют разные алгоритмы для преобразования регулярных выражений в конечные автоматы. Вы можете перейти непосредственно от регулярных выражений к DFA, не создавая сначала никакого другого автомата, неявно выполняя конструкцию подмножества при генерации автомата. Другим вариантом прямого получения детерминированных автоматов является использование метода производных.

Проверка того, представляет ли регулярное выражение язык, содержащий все строки, является полной проблемой PSPACE (см. Этот ответ для справки). Проверка того, что DFA принимает этот язык, может быть выполнена за полиномиальное время, поэтому, если вы перейдете непосредственно от регулярного выражения к DFA, где-то произойдет взрыв.

Я понимаю литературу, что мы можем выбрать переводы, которые позволят нам локализовать взрыв. Это означает, что существуют разные способы перехода от регулярного выражения к конечному автомату, и предпочтительны линейные или полиномиальные методы. Обычно экспоненциальные издержки подталкиваются к определению автоматов.

Была проделана большая работа по выявлению подсемей регулярных выражений, из которых мы можем эффективно генерировать DFA. Это направление работы зависит от используемого вами перевода. Это означает, что вы исправляете отображение регулярных выражений в NFA и пытаетесь охарактеризовать регулярные выражения, которые отображаются в DFA.

Стандартная конструкция автоматов из регулярных выражений не является предпочтительной конструкцией в такой работе. Выбранные конструкции создают автоматы, которые очень похожи на структуру регулярного выражения. В этих конструкциях используется понятие производной регулярного выражения.

Производные регулярных выражений , Я. А. Бжозовский. 1964.

sрaрa

Частичные производные регулярных выражений и конструкции конечных автоматов , В. Антимиров. 1995.

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

От регулярных выражений до детерминированных автоматов , Г. Берри и Р. Сетхи, 1986.

Соответствие между регулярными выражениями и состояниями автомата и детерминизма явно обсуждается Берри и Сетхи, которые объединяют понятие производных Бжозовского с идеей различения вхождений одного и того же символа, чтобы дать основанный на синтаксисе перевод регулярных выражений в конечные автоматы.

Однозначные регулярные языки , А. Брюггеманн-Кляйн и Дерик Вуд, 1998.

Эта статья основана на более ранней работе Брюггеманна-Кляйна и изучает случаи, в которых вы можете использовать производные для генерации DFA за полиномиальное время. После этой работы проделана большая работа. Это было важно с точки зрения веб-технологий, потому что регулярные выражения, которыми можно эффективно управлять (иначе говоря, соответствующие DFA), были важны для обработки SGML и XML.

Было много работы по изучению других частных случаев детерминированных регулярных выражений. Самая недавняя статья, в которой изучается, когда некоторые из этих проблем могут быть решены за линейное время, относится к 2012 году.

Детерминированные регулярные выражения в линейном времени , Бенуа Гроз, Себастьян Манет, Славомир Ставорко. 2012.

Виджай Д
источник
5
Вы уже упомянули производные в своем ответе, поэтому вы должны также добавить JA Brzozowski: Производные регулярных выражений, Журнал ACM 11 (4): 481–494 (1964), так как он дает прямой алгоритм для преобразования регулярных выражений в DFA ,
Нил Кришнасвами,
3
Я спорил об этом. Но все три статьи, приведенные выше, напрямую основаны на этом результате, поэтому я подумал, что нет причин упоминать об этом. Бумага Брейггемана-Кляйна и Вуда полна примеров. Если я упомяну Бжозовского, я чувствую, что следует упомянуть и Антимирова. Я хотел избежать опроса, но, возможно, я должен просто пойти на это. Что сказать?
Виджай Д
5
Если у вас есть время и энергия, я думаю, что длинные ответы, подобные опросам, очень уместны здесь.
Дэвид Эппштейн
1
@VijayD: да, я согласен с Дэвидом. Короткие ответы - это хорошо, но если у вас есть энергия, было бы хорошо дать исчерпывающий ответ.
Нил Кришнасвами