Jak utworzyć związek dwóch DFA?

Question

Czy ktoś ma prosty opis algorytmu do budowy związku dwóch danych DFA? Na przykład, powiedzmy mamy dwa DFA nad {0,1}, gdzie

{w|w has an odd number of characters} 
    w has states A and B 

delta | 0 | 1 
---------------- 
    A | B | B 
---------------- 
    B | A | A 


{x|x has an even number of 1s} 
    x has states a and b 

delta | 0 | 1 
---------------- 
    a | a | b 
---------------- 
    b | b | a 

mam wynikowa tabela pokazuje przejście do unii jako:

delta | 0 | 1 
---------------- 
    Aa | Ba | Bb 
---------------- 
    Ab | Bb | Ba 
---------------- 
    Ba | Aa | Ab 
---------------- 
    Bb | Ab | Aa 

Mam obrazowym rozwiązanie w moich notatek, ale chciałbym zobaczyć, jak inni by to opisali. Z tego widać, że zasadniczo "pomnażamy" te dwie oryginalne tabele, używając ich wartości stanu, aby uzyskać większą tabelę przejściową. DFA można w ten sposób wyciągnąć z wynikowej tabeli. Czy to brzmi dobrze i czy to powinno działać we wszystkich przypadkach DFA, czy jest coś, czego mi brakuje?

Answer 1

Kluczem do zrozumienia jest to, że musisz uruchomić oba DFA jednocześnie lub ogólnie musisz zachować stany obu DFA w unii DFA.

Dlatego musisz stworzyć nowe stany dla związku DFA jako bezpośrednie zwielokrotnienie oryginalnych stanów. W ten sposób masz stan dla każdej kombinacji stanów w oryginalnych DFA.

Reguły przejścia dla nowego DFA można bezpośrednio obliczyć. Na przykład, jeśli jesteś w stanie Ab, a otrzymasz 0 na wejściu, pierwszy DFA przejdzie do stanu B, a drugi do stanu b, więc następny stan unii DFA dla tego wejścia będzie Bb.

Ta metoda działa w każdym przypadku, gdy konieczne jest połączenie dwóch lub więcej DFA. Wynikowy DFA może nie być optymalny, ale później można go zminimalizować za pomocą dowolnego algorytmu.