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

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

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

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

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

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

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

$$u^{-1}L = \{v \in A^* \mid uv \in L \}$$ $u^{-1}L$$L$

Неродный автомат . Nerode автомат из является детерминированным автоматом ( L ) = ( Q , , ⋅ , L , F ) , где Q = { у - 1 л | у ∈ * } , Р = { у - 1 л | U ∈ L } и определена функция перехода для каждого a $L$$\mathcal{A}(L) = (Q, A, \cdot, L, F)$$Q = \{u^{-1}L \mid u \in A^*\}$$F = \{u^{-1}L \mid u \in L\}$ , по формуле ( u - 1 L ) ⋅ a = a - 1 ( u - 1 L ) = ( u a ) - 1 L Остерегайтесь этого довольно абстрактного определения. Каждое состояние A является левым частным L по слову и, следовательно, является языком A ∗ . Начальное состояние языка L , и множество конечных состояний есть множество всех левых частных L по слову L .$a \in A$

$$(u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L$$ $\mathcal{A}$$L$$A^*$$L$$L$$L$

$a, b$

$$\begin{align*} a^{-1}1 &= 0 & a^{-1}b &= \begin{cases} 1 &\text{if $a = b$}\\ 0 &\text{if $a \not= b$}\\ \end{cases}\\ a^{-1}(L_1 \cup L_2) &= a^{-1}L_1 \cup u^{-1}L_2,& a^{-1}(L_1 \setminus L_2) &= a^{-1}L_1 \setminus u^{-1}L_2,\\ a^{-1}(L_1 \cap L_2) &= a^{-1}L_1 \cap u^{-1}L_2, & a^{-1}L^* &= (a^{-1}L)L^* \end{align*}$$ $$\begin{align*} a^{-1}(L_1L_2) &= \begin{cases} (a^{-1}L_1)L_2 &\text{si $1 \notin L_1$,}\\ (a^{-1}L_1)L_2 \cup a^{-1}L_2 &\text{si $1 \in L_1$}\\ \end{cases}\\ %\\v^{-1}(u^{-1}L) &= (uv)^{-1}L. \end{align*}$$

$L = (a(ab)^*)^* \cup (ba)^*$

$$\begin{align*} 1^{-1}L &= L=L_1\\ a^{-1}L_1 &=(ab)^*(a(ab)^*)^*=L_2\\ b^{-1}L_1 &= a(ba)^*=L_3\\ a^{-1}L_2 &= b(ab)^*(a(ab)^*)^* \cup (ab)^*(a(ab)^*)^*=bL_2 \cup L_2=L_4\\ b^{-1}L_2 &=\emptyset \\ a^{-1}L_3 &=(ba)^*=L_5\\ b^{-1}L_3 &=\emptyset \\ a^{-1}L_4 &= a^{-1}(bL_2 \cup L_2)=a^{-1}L_2=L_4 \\ b^{-1}L_4 &= b^{-1}(bL_2 \cup L_2)= L_2\cup b^{-1}L_2 = L_2 \\ a^{-1}L_5 &= \emptyset\\ b^{-1}L_5 &=a(ba)^*=L_3 \end{align*}$$

$[1]$

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

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

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

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

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

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

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

$P=NP=PSPACE$

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

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

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

Например: регулярное выражение (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.