Skuteczne połączenie DFA?

16

Istnieją teoretyczne dowody na to, że naiwna konstrukcja produktu kartezjańskiego na przecięciu DFA jest „najlepsza, co możemy zrobić”. Co z konkatenacją dwóch DFA? Trywialna konstrukcja polega na przekształceniu każdego DFA w NFA, dodaniu przejścia epsilon i określeniu wynikowego NFA. Czy możemy zrobić lepiej? Czy znane jest ograniczenie wielkości minimalnej DFA konkatenacji (pod względem wielkości DFA „przedrostka” i „sufiksu”)?

Aryeh
źródło

Odpowiedzi:

20

Tak - wiadomo, że istnieją DFA odpowiednio dla stanów i n , tak że minimalny DFA dla konkatenacji odpowiednich języków ma m 2 n - 2 n - 1 stanów, które pasują do znanej górnej granicy.mnm2)n-2)n-1

Po raz pierwszy zaobserwował to Masłow w 1970 r., A ponownie odkryli je Yu, Zhuang i K. Salomaa w swojej pracy „Złożoność państwowa niektórych podstawowych operacji na zwykłych językach”, TCS 125 (1994), 315-328.

Jeffrey Shallit
źródło
1
Dzięki, Jeffrey! Czy ten automat można zbudować w czasie krócej niż banalnieO(2)n+m)?
Aryeh
1
Jeśli spojrzysz na cytowany przeze mnie artykuł, zobaczysz konstrukcję i wydaje mi się, że można ją zbudować zasadniczo w tym samym czasie co liczba stanów, m2)n-2)n-1.
Jeffrey Shallit