Как создать DFA из регулярного выражения без использования NFA?

12

Цель состоит в том, чтобы создать DFA из регулярного выражения, и использование «Regular exp> NFA> DFA преобразование» не вариант. Как это сделать?

Я задал этот вопрос нашему профессору, но он сказал мне, что мы можем использовать интуицию, и любезно отказался дать какие-либо объяснения. Поэтому я хотел спросить вас.

«Преобразование регулярного exp> NFA> DFA» не является опцией, потому что такое преобразование занимает много времени для преобразования довольно сложного регулярного выражения. Например, для определенного регулярного выражения "регулярное выражение> NFA> DFA" человеку требуется 1 час. Мне нужно преобразовать регулярное выражение в DFA менее чем за 30 минут.

Рафаэль
источник
2
Вы должны предоставить больше контекста. Какой (неформальный) алгоритм вы сейчас используете для перевода регулярных выражений? Может быть полезно объяснить ваш процесс на примере, например a(a|ab|ac)*a+. Вы можете либо напрямую перевести это в NDFA, который вы уменьшаете до DFA, либо вы можете нормализовать его к чему-то, что немедленно отображается в DFA.
Am
Нужно ли вам делать это на конкретных примерах какими-либо средствами, или вы должны предоставить общую процедуру, которая будет применяться компьютером?
Бабу

Ответы:

18

Поскольку вы хотите «преобразовать регулярные выражения в DFA менее чем за 30 минут», я полагаю, вы работаете вручную над сравнительно небольшими примерами.

В этом случае вы можете использовать алгоритм Бжозовского , который вычисляет непосредственно автомат Нерода языка (который, как известно, равен его минимальному детерминированному автомату). Он основан на прямом вычислении производных, а также работает для расширенных регулярных выражений, допускающих пересечение и дополнение. Недостаток этого алгоритма состоит в том, что он требует проверки эквивалентности выражений, вычисленных по пути, дорогостоящего процесса. Но на практике и для небольших примеров это очень эффективно.[1]

Левые коэффициенты . Пусть язык A ∗, а u слово. Тогда у - 1 л = { v * | U v L } Язык у - 1 л называется левый фактор (или левой производной ) из L .LA*U

U-1Lзнак равно{vA*|UvL}
U-1LL

Неродный автомат . Nerode автомат из является детерминированным автоматом ( L ) = ( Q , , , L , F ) , где Q = { у - 1 л | у * } , Р = { у - 1 л | U L } и определена функция перехода для каждого a LA(L)знак равно(Q,A,,L,F)Qзнак равно{U-1L|UA*}Fзнак равно{U-1L|UL} , по формуле ( u - 1 L ) a = a - 1 ( u - 1 L ) = ( u a ) - 1 L Остерегайтесь этого довольно абстрактного определения. Каждое состояние A является левым частным L по слову и, следовательно, является языком A . Начальное состояние языка L , и множество конечных состояний есть множество всех левых частных L по слову L .aA

(U-1L)aзнак равноa-1(U-1L)знак равно(Ua)-1L
ALA*LLL

a,б

a-11знак равно0a-1бзнак равно{1если aзнак равноб0если aбa-1(L1L2)знак равноa-1L1U-1L2,a-1(L1L2)знак равноa-1L1U-1L2,a-1(L1L2)знак равноa-1L1U-1L2,a-1L*знак равно(a-1L)L*
a-1(L1L2)знак равно{(a-1L1)L2си 1L1,(a-1L1)L2a-1L2си 1L1

Lзнак равно(a(aб)*)*(бa)*

1-1Lзнак равноLзнак равноL1a-1L1знак равно(aб)*(a(aб)*)*знак равноL2б-1L1знак равноa(бa)*знак равноL3a-1L2знак равноб(aб)*(a(aб)*)*(aб)*(a(aб)*)*знак равнобL2L2знак равноL4б-1L2знак равноa-1L3знак равно(бa)*знак равноL5б-1L3знак равноa-1L4знак равноa-1(бL2L2)знак равноa-1L2знак равноL4б-1L4знак равноб-1(бL2L2)знак равноL2б-1L2знак равноL2a-1L5знак равноб-1L5знак равноa(бa)*знак равноL3
Минимальный автомат

[1]

Редактировать . (5 апреля 2015 г.) Я только что обнаружил, что похожий вопрос: какие существуют алгоритмы для построения DFA, который распознает язык, описываемый данным регулярным выражением? был задан вопрос по истории. Ответ частично решает проблемы сложности.

J.-E. Штырь
источник
Можете ли вы сказать больше о сложности этого алгоритма?
Бабу
@babou Преобразование RE в DFA является сложным для PSPACE, поэтому оно определенно экспоненциальное.
jmite
Это, вероятно, должно идти в ответ. ОП начинается с «стандартных конструкций через NFA слишком медленные», и часть ответа кажется «неудачей, на самом деле быстрого решения не существует». Осталось обсудить, лучше ли это здесь, чем стандартная конструкция. (cc @jmite)
Рафаэль
@jmite Да, я ожидал этого. Причина моего вопроса заключается в том, почему этот способ построения DFA следует рассматривать проще. (примечание: системе потребовался целый день, чтобы уведомить меня о ответе @ jmite).
Бабу
2

J.-E. Пин дает лучший ответ с точки зрения формальности и полноты, но я думаю, что есть кое-что, что можно сказать о «интуиции», на которую намекает ваш профессор.

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

Нет простого способа сделать это, кроме алгоритмов, которые дали другие, но вот некоторые рекомендации, которые могут оказаться полезными.

  1. Спросите себя, могу ли я написать программу, которая принимает этот RE, используя только логические или очень маленькие целочисленные переменные? Затем напишите эту программу и преобразуйте ее в DFA, где есть состояние для каждой комбинации значений.

  2. Ищите части регулярного выражения, которые, как вы знаете, вы можете принять детерминистически, где вы знаете: «Если я это увижу, то я должен соответствовать этой части RE». Их не всегда будет много, но идентификация этих частей может показать части, которые будет легко создать DFA, так что вы можете потратить больше времени на части, которые действительно требуют недетерминизма.

  3. Построение подмножества для NFA-> DFA на самом деле не так уж сложно в алгоритме. Так что, если это задание, а не экзаменационный вопрос, может быть быстрее просто кодировать реализацию и позволить вашей программе преобразовывать NFA в DFA. Если вы использовали свой собственный код, не должно быть никаких проблем с плагиатом.

пзнак равноNпзнак равнопSпAСЕ

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

jmite
источник
-2

Хотя это не правильный путь, но он работает большую часть времени.

Первый шаг : найдите наименьшую строку, которая может быть принята регулярным выражением. Второй шаг : нарисуйте необходимые состояния с помощью транзакции машины, принимающей минимальную строку. Третий шаг : для всех штатов нарисуйте оставшиеся алфавиты транзакций.

Например: регулярное выражение (0 + 1) * 1 "Строка, заканчивающаяся 1" Шаг 1: Наименьшая строка: 1 Шаг 2: два состояния Q0 и Q1. имея транзакцию 1 от Q0 до Q1. и Q1 - принимающее состояние. Шаг 3: для Q0-состояния Q0 1 транзакция идет в Q1. Теперь сделайте 0 транзакцию в самом Q0. Для Q1 State Q1 1 транзакция останется в Q1. И 0 транзакция пойдет в Q0.

Навин CS
источник