Skuteczne połączenie DFA?

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”)?

cc.complexity-theory fl.formal-languages automata-theory dfa Aryeh
źródło

Odpowiedzi:

Tak - wiadomo, że istnieją DFA odpowiednio dla stanów i , tak że minimalny DFA dla konkatenacji odpowiednich języków ma stanów, które pasują do znanej górnej granicy. $m$ $n$ $m*2^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

Dzięki, Jeffrey! Czy ten automat można zbudować w czasie krócej niż banalnie

O (2^{n + m})

$O(2^{n+m})$ ?

Aryeh

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,

m * 2^{n} - 2^{n - 1}

$m*2^n - 2^{n-1}$ .

Jeffrey Shallit