Znane algorytmy przechodzenia z DFA do wyrażenia regularnego

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.$\mathcal{A}$$r$$L(\mathcal{A})=L(r)$$R_{ij}^k$$q_i$$q_j$$k$

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ę).$\varepsilon$

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!

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.

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 \times 2$

$\begin{bmatrix} a & b \\ c & d \end{bmatrix}^* = \begin{bmatrix} (a+bd^*c)^* & (a+bd^*c)^*bd^* \\ (d+ca^*b)^*ca^* & (d+ca^*b)^* \end{bmatrix}$

$i,j$$i$$j$

$n \times n$$a,b,c,d$$m\times m$$m\times (n-m)$$(n-m) \times m$$(n-m) \times (n-m)$$2 \times 2$$2 \times 2$

$n$$T$$\sum_{f \in F} (T^*)_{s,f}$$s$$T^*$

$m=1$$R_{ij}^k$

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

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.