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

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.

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 A * i niech u być słowo. Następnie u - 1 L = { v ∈ * | u , v ∈ L } Język u - 1 l nazywa się lewy iloraz (lub po pochodnej ) z L .$L$$A^*$$u$

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

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

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. 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.

1. 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.

2. 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.

3. 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.

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.