Jak utworzyć DFA z wyrażenia regularnego bez użycia NFA?

12

Celem jest utworzenie DFA z wyrażenia regularnego, a użycie opcji „Regular exp> NFA> Konwersja DFA” nie jest opcją. Jak należy to zrobić?

Zadałem to pytanie naszemu profesorowi, ale powiedział mi, że możemy korzystać z intuicji i uprzejmie odmówił podania jakichkolwiek wyjaśnień. Więc chciałem cię zapytać.

Opcja „Regular exp> NFA> Konwersja DFA” nie jest opcją, ponieważ taka konwersja zajmuje dużo czasu, aby przekonwertować dość złożone wyrażenie regularne. Na przykład dla pewnego wyrażenia regularnego „wyrażenie regularne> NFA> DFA” zajmuje człowiekowi 1 godzinę. Muszę przekonwertować wyrażenie regularne na DFA w mniej niż 30 minut.

— Raphael
źródło

2

Musisz podać więcej kontekstu. Jakiego (nieformalnego) algorytmu używasz obecnie do tłumaczenia wyrażeń regularnych? Pomocne może być wyjaśnienie procesu na przykładzie takim jak a(a|ab|ac)*a+. Możesz albo bezpośrednio przetłumaczyć to na NDFA, które redukujesz do DFA, albo możesz znormalizować to do czegoś, co mapuje natychmiast do DFA.

— amon

Czy musisz to robić na konkretnych przykładach za pomocą dowolnych środków, czy też musisz podać ogólną procedurę. Do zastosowania przez komputer?

— babou

18

Ponieważ chcesz „przekonwertować wyrażenie regularne na DFA w mniej niż 30 minut”, przypuszczam, że pracujesz ręcznie na stosunkowo małych przykładach.

W tym przypadku można zastosować algorytm Brzozowskiego , który bezpośrednio oblicza automat Nerode języka (o którym wiadomo, że jest równy minimalnemu automatowi deterministycznemu). Opiera się na bezpośrednim obliczeniu pochodnych, a także działa na rozszerzone wyrażenia regularne, umożliwiające przecięcie i uzupełnienie. Wadą tego algorytmu jest to, że wymaga sprawdzenia równoważności wyrażeń obliczanych po drodze, kosztownego procesu. Ale w praktyce i dla małych przykładów jest bardzo wydajny. $[1]$

Lewe ilorazy . Niech będzie językiem i niech być słowo. Następnie Język nazywa się lewy iloraz (lub po pochodnej ) z . $L$ $A^*$ $u$

u^{- 1} L = {v \in A^{*} ∣ u v \in L}

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

u^{- 1} L

$u^{-1}L$

L

$L$

Automat Nerode . Automat Nerode z jest deterministyczny automat , gdzie , i funkcja przejścia jest zdefiniowana dla każdego $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\}$ według wzoru Strzeż się tej raczej abstrakcyjnej definicji. Każdy stan jest lewym ilorazem słowa, a zatem jest językiem . Początkowy stan jest język i zbiorem stanów końcowych jest zbiorem wszystkich pozostawionych ilorazów przez słowo . $a \in A$

(u^{- 1} L) \cdot a = a^{- 1} (u^{- 1} L) = (u a)^{- 1} L

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

A

$\mathcal{A}$

L

$L$

A^{*}

$A^*$

L

$L$

L

$L$

L

$L$

$a, b$

\begin{aligned} a^{- 1} 1 & = 0 & a^{- 1} b & = {\begin{cases} 1 & if a = b \\ 0 & if a \neq b \end{cases} \\ a^{- 1} (L_{1} \cup L_{2}) & = a^{- 1} L_{1} \cup u^{- 1} L_{2}, & a^{- 1} (L_{1} ∖ L_{2}) & = a^{- 1} L_{1} ∖ 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{aligned}

$\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{aligned} a^{- 1} (L_{1} L_{2}) & = {\begin{cases} (a^{- 1} L_{1}) L_{2} & si 1 \notin L_{1}, \\ (a^{- 1} L_{1}) L_{2} \cup a^{- 1} L_{2} & si 1 \in L_{1} \end{cases} \end{aligned}

$\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{aligned} 1^{- 1} L & = L = L_{1} \\ a^{- 1} L_{1} & = (a b)^{*} (a (a b)^{*})^{*} = L_{2} \\ b^{- 1} L_{1} & = a (b a)^{*} = L_{3} \\ a^{- 1} L_{2} & = b (a b)^{*} (a (a b)^{*})^{*} \cup (a b)^{*} (a (a b)^{*})^{*} = b L_{2} \cup L_{2} = L_{4} \\ b^{- 1} L_{2} & = \emptyset \\ a^{- 1} L_{3} & = (b a)^{*} = L_{5} \\ b^{- 1} L_{3} & = \emptyset \\ a^{- 1} L_{4} & = a^{- 1} (b L_{2} \cup L_{2}) = a^{- 1} L_{2} = L_{4} \\ b^{- 1} L_{4} & = b^{- 1} (b L_{2} \cup L_{2}) = L_{2} \cup b^{- 1} L_{2} = L_{2} \\ a^{- 1} L_{5} & = \emptyset \\ b^{- 1} L_{5} & = a (b a)^{*} = L_{3} \end{aligned}

$\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*}$ Minimalny automat

$[1]$

Edit . (5 kwietnia 2015 r.) Właśnie odkryłem, że podobne pytanie: jakie algorytmy istnieją do budowy DFA, który rozpoznaje język opisany przez dane wyrażenie regularne? został zapytany na cstheory. Odpowiedź częściowo rozwiązuje problemy ze złożonością.

— J.-E. Kołek
źródło

Czy możesz powiedzieć więcej o złożoności tego algorytmu?

— babou

@babou Przekształcenie RE w DFA jest trudne dla PSPACE, więc jest zdecydowanie wykładnicze.

— jmite

To prawdopodobnie powinno znaleźć się w odpowiedzi. OP zaczyna się od „standardowych konstrukcji przez NFA są zbyt wolne”, a część odpowiedzi wydaje się brzmieć „pech, nie ma tak naprawdę szybkiego rozwiązania”. Pozostaje do omówienia, czy tutaj jest to lepsze niż standardowa konstrukcja. (cc @jmite)

— Raphael

@jmite Tak, spodziewałem się tego. Powodem mojego pytania jest to, dlaczego ten sposób budowania DFA należy uznać za łatwiejszy. (uwaga: system poświęcił cały dzień na powiadomienie mnie o odpowiedzi @ jmite).

— babou

2

J.-E. Pin zapewnia lepszą odpowiedź pod względem formalności i kompletności, ale myślę, że można powiedzieć coś o „intuicji”, na którą wskazuje twój profesor.

W większości tych przypadków najłatwiej jest spojrzeć na wyrażenie regularne, zrozumieć, jaki język akceptuje, a następnie wykorzystać swoją kreatywność / spryt, aby zbudować DFA akceptujący ten język.

Nie ma prostego sposobu, aby to zrobić, oprócz algorytmów podanych przez innych, ale oto kilka wskazówek, które mogą się okazać przydatne.

Zadaj sobie pytanie, czy mógłbym napisać program, który akceptuje to RE, używając tylko zmiennych boolowskich lub bardzo małych liczb całkowitych? Następnie napisz ten program i przekonwertuj go na DFA, w którym istnieje stan dla każdej kombinacji wartości.
Poszukaj części wyrażenia regularnego, które możesz zaakceptować deterministycznie, gdzie wiesz, że „Jeśli to widzę, to muszę dopasować tę część RE”. Nie zawsze będzie ich mnóstwo, ale identyfikacja tych części może pokazać części, które będą łatwe do stworzenia DFA, dzięki czemu możesz spędzić więcej czasu na częściach, które naprawdę wymagają niedeterminizmu.
Konstrukcja podzbioru dla NFA-> DFA nie jest tak skomplikowana jak algorytm. Więc jeśli jest to zadanie, a nie pytanie egzaminacyjne, może być szybsze kodowanie implementacji i pozwolenie Twojemu programowi na konwersję NFA na DFA. Jeśli użyłeś własnego kodu, nie powinno być żadnych problemów z plagaryzmem.

$P=NP=PSPACE$

Spróbuj „patrzeć przed siebie”, skracając rogi, gdy możesz używać intuicji w miejscach, w których algorytm wymagałby wielu kroków, ale jego wynik jest jasny.

— jmite
źródło

-2

Chociaż nie jest to właściwy sposób, ale działa przez większość czasu.

Pierwszy krok : znajdź najmniejszy ciąg znaków, który może zostać zaakceptowany przez wyrażenie regularne. Drugi krok : narysuj niezbędne stany za pomocą transakcji minimalnego ciągu akceptującego ciąg. Trzeci krok : dla wszystkich stanów narysuj pozostałe transakcje alfabetyczne.

Na przykład: Wyrażenie regularne (0 + 1) * 1 ”Łańcuch kończący się na 1” Krok 1: Najmniejszy ciąg: 1 Krok 2: dwa stany Q0 i Q1. z transakcją 1 od Q0 do Q1. a Q1 to stan akceptujący. Krok 3: dla stanu Q0 transakcja Q0 1 odbywa się do pierwszego kwartału. Teraz dokonaj transakcji 0 w samym Q0. Dla stanu w pierwszym kwartale transakcja w pierwszym kwartale pozostanie w pierwszym kwartale. I 0 transakcji pójdzie w Q0.

— Naveen CS
źródło