Znane algorytmy przechodzenia z DFA do wyrażenia regularnego

28

Zastanawiałem się, czy istnieje `` lepszy '' (wyjaśnię, w jakim sensie) algorytm rozpoczynający się od DFA i konstruujący wyrażenie regularne r takie, że L ( A ) = L ( r ) , niż ten w książka Hopcroft i Ullman (1979). Tam, zbiory R k i j są używane do reprezentowania komplety strun, które odbywają się od stanu DFA q I do q j bez przechodzenia przez stan numerach wyższa niż k . Ta konstrukcja, choć oczywiście poprawna i bardzo przydatna, jest raczej techniczna.ArL(A)=L(r)Rijkqiqjk

Piszę monografię na temat teorii algebraicznych automatów i nie chcę rozpraszać moich odbiorców zbyt wieloma szczegółami technicznymi (przynajmniej nie szczegółami, które nie mają znaczenia dla wyników, które chcę pokazać), ale chcę dołączyć dowód równoważności DFA i wyrażeń regularnych w celu zapewnienia kompletności. Dla przypomnienia, używam automatów Glushkov, aby przejść z wyrażenia regularnego do DFA. Wydawało się to bardziej intuicyjne niż przejścia, których w ogóle nie zdefiniowałem (znowu, ponieważ ich nie potrzebuję).ε

Jakie inne algorytmy są znane z przejścia z DFA na wyrażenie regularne? Cenię prostotę nad wydajnością (w tym przypadku jest to dla mnie `` lepsze ''), ale nie jest to wymóg.

Z góry dziękuje za twoją pomoc!

Janoma
źródło
1
Nie jest to inny algorytm, ale algorytm można wyrazić algebraicznie, używając k- tej potęgi macierzy wyrażeń regularnych w odpowiedniej algebrze. Być może znajdziesz to bardziej eleganckie / zwięzłe. Szukam referencji. Rijkk
Maks.
1
algorytm jest w istocie wariantem Algorytm Floyda-Warshalla dla problemu All-par-najkrótszej ścieżki, więc można znaleźć prezentację pod względem mnożenia macierzy szukając tych słów kluczowych. Rijk
Jan Johannsen,
2
Zgadzam się. Jest to w zasadzie algorytm Floyda-Warshalla. Można go również uzyskać za pomocą standardowych technik programowania dynamicznego (podobnie jak Floyd-Warshall).
David
Jestem pewien, że wcześniej odpowiedziałem na takie pytanie, ale nie mogę go znaleźć.
Raphael,
@Max czy możesz znaleźć referencję? Interesuje mnie reprezentacja macierzy, powinna być bardziej atrakcyjna dla algebry.
Janoma,

Odpowiedzi:

17

Dwie kolejne konstrukcje: eliminacja stanu Brzozowskiego-McCluskeya, czyli aka eliminacja stanu [1], oraz eliminacja Gaussa w układzie równań z wykorzystaniem Lemmy Ardena. Najlepszym źródłem na ten temat jest prawdopodobnie książka Jacquesa Sakarovitcha [2].

[1] J. Brzozowski, E. McCluskey Jr., Techniki grafów przepływowych dla diagramów stanów obwodu sekwencyjnego, Transakcje IEEE na komputerach elektronicznych EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elementy teorii automatów. Cambridge University Press, 2009.

Sylvain
źródło
2
Podejście polegające na rozwiązywaniu równań za pomocą lematu Ardena uważam za najprostsze i najłatwiejsze do wyjaśnienia, dlatego przedstawiam to w ten sposób na zajęciach z teorii wprowadzającej.
Jan Johannsen,
Metoda układu równań brzmi genialnie. Niestety, biblioteka mojego uniwersytetu nie ma książki, o której wspominasz (Sakarovitch), ale zamierzam szukać gdzie indziej.
Janoma,
4
Porównanie konstrukcji znajduje się także w pracy Sakarovitcha „Język, ekspresja i (mały) automat”, CIAA 2005, LNCS 3845, Springer (2006) 15-30. Zobacz infres.enst.fr/~jsaka/PUB/Files/LESA.pdf
Hermann Gruber
2
Zauważ też, że kolejność przetwarzania stanów może znacznie wpłynąć na rozmiar wynikowego wyrażenia regularnego. Dotyczy to zawsze prawdy: czy robisz to z lematem Ardena, McNaughton-Yamada, eliminacją stanu, czy innym wariantem. Dostępnych jest kilka prostych heurystyk służących do wyboru dobrego uporządkowania eliminacji.
Hermann Gruber,
15

Książka Kozen „Automata i obliczalność” wspomina o eleganckim uogólnieniu tego algorytmu Floyda-Warshalla. Ponieważ wspomniałeś o odwoływaniu się do algebraistów, może ci się to przydać. Znajdziesz go na stronach 58–59 tego tekstu. (Myślę, że książki Google mają podgląd).

2×2

[abcd]=[(a+bdc)(a+bdc)bd(d+cab)ca(d+cab)]

i,jij

n×na,b,c,dm×mm×(nm)(nm)×m(nm)×(nm)2×22×2

nTfF(T)s,fsT

m=1Rijk

Kolejne wyprowadzenie struktur algebry Kleene'a nad macierzami pojawia się w Twierdzeniu o kompletności dla Kleene Algebras i Algebrze regularnych zdarzeń Kozen'a.

mikero
źródło
12

Zdecydowanie najładniejsza procedura, jaką widziałem, to wspomniana przez Sylvaina. W szczególności wydaje się, że daje więcej zwięzłych wyrażeń niż inne.

Napisałem ten dokument wyjaśniający metodę dla studentów zeszłego lata. Odnosi się bezpośrednio do konkretnego wykładu; wspomniane odniesienie jest typową definicją wyrażeń regularnych. Dowód lematu Ardena jest zawarty; brakuje jednego dla poprawności metody. Jak dowiedziałem się o tym na wykładzie, niestety nie mam odniesienia.

Raphael
źródło
Ja też wolę ten dowód. Uważam to za eleganckie i łatwe do wyjaśnienia. Nawet lemat Ardena nie jest trudny. Myślę, że będzie to metoda, którą uwzględnię w moim dokumencie.
Janoma,
+