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.
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!
Odpowiedzi:
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.
źródło
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).
Kolejne wyprowadzenie struktur algebry Kleene'a nad macierzami pojawia się w Twierdzeniu o kompletności dla Kleene Algebras i Algebrze regularnych zdarzeń Kozen'a.
źródło
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.
źródło