Łączenie deterministycznych automatów skończonych

Question

Jestem naprawdę nowy w tych rzeczach, więc przepraszam za nieobliczalność.

skonstruować Deterministic Finite Automaton DFA uznając następujący język:

L= { w : w has at least two a's and an odd number of b's}. 

Automatyzacja dla każdej części tej (at least 2 a's, odd # of b's) są łatwe do wykonania osobno ... Czy ktoś proszę wyjaśnić systematyczny sposób, aby połączyć je w jeden? Dzięki.

Answer 1

Jest to wykonywane przy użyciu product dwóch automatów.

Answer 2

Język L gdzie a są co najmniej dwa, a b są dziwne to język regularny. Jego DFA jest jak poniżej:

W tym DFA I połączyli dwa DFS s koncepcyjnie!

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram) 
DFA-2 = for >= two a   (placed Horizontally two times in diagram) 

_{DFA jest zbyt objawowe i proste więc wierzę, nie ma potrzeby w słowa, które jak łączyć zarówno DFAS}

Aby narysować ten DFA jesteś zawsze śledzić ilu b s został pochodzić parzyste czy nieparzyste. States 0, 2 and 4 oznacza, że ​​nadszedł jeszcze numer b. Tak więc możesz podzielić ten DFA na dwie części pionowo, gdzie dolne stany mają nawet b s a górne stany są nieparzyste.

Również łańcuch jest akceptowany, jeśli nieparzysty b, dlatego stan końcowy powinien znajdować się w stanie w górnej części.

nie tylko liczba b s jest warunek ale a powinny być conajmniej 2. Więc można podzielić ten DFA poziomo na trzy części, w których liczba a s są 0 w state-0 and 1, a s są pojedynczo state-2 and 3 i a s są 2 na state-4 and 5. Po pierwszych dwóch a s dowolnej liczbie a s są dozwolone w łańcuchu, więc istnieje samo pętla w stanie q4 i q5.

_{numer stanu wymagane jest sześć, ponieważ 2 stopnie dla nieparzystych nawet b, jak hould się conajmniej 2 więc trzy stany: a = 0, a = 1, A = 2, w związku 2 * 3 = 6}

Answer 3

Możesz użyć następujących prostych kroków, aby utworzyć połączone DFA.

Niech Σ = {a , A , ..., a _k}.
1. krok: Projekt DFA dla obu języków i nazwać ich stan Q , Q ...

2. krok: Zmień nazwę każdego stanu zarówno w DFA jednoznacznie tjnazwy wszystkich stanów w DFA jako Q , Q , Q , Q ... zakładając, że zaczęli z indeksem 0; to znaczy, że żadne państwo nie będzie miało tego samego imienia.

Etap 3: tabeli przejście budynku (δ) stosując następujące etapy

      3a. Uruchom stan połączonego DFA:
            Take stan początkowy zarówno DFAS (DFA1 i DFA2) i wymienić je jako Q _{[i, j]} gdzie i oraz j oznaczają indeks stanu początkowego Odpowiednio DFA1 i DFA2; to Q _i jest stan początkowy DFA z 1 i Q _J jest stan początkowy z 2 DFA i znak Q _{[i, j]} jak stanu początkowego kombinowanego DFA.

      3b. Stan Mapa zarówno DFAS jak
                      jeśli δ (P _i, A _K) = P _P1 i δ (P _J, A _K) = Q _P2, gdzie Q _P1 należy do DFA1 i Q _{Pnależy do DFA2 następnie   δ (P [i, j], A K) = P [p1, p2]}

      3c. wypełnij całą tabelę, podczas gdy w tabeli przejściowej pozostanie jeszcze jeden Q _{[i, j]}.

      3d. Stan końcowy połączonej DFA:
            Na AND przypadku stan końcowy będzie wszystkie P _{[i, j]} którym Q _i i Q _J jest stan końcowy DFA1 i DFA2 odpowiednio.
            Na OR przypadku stan końcowy będzie wszystkie P _{[i, j]} którym albo Q _i lub Q _J jest stan końcowy DFA1 i DFA2.

4. krok: nazwy wszystkich Q _{[i, j]} (wyjątkowo) i wyciągnąć DFA to będzie twój wynik.

przykład:

L= {w: w has at least two a's and an odd number of b's}. 

Etap 1:
DFA dla nieparzystej liczby b,.

DFA przez co najmniej 2 a-tych.

Etap 2:
zmienić nazwę Stae z DFA1

Krok 3 (a, b, c)
Wykonany tabeli przejściowy być.

Step3d:
Ponieważ mamy do pobierania i zarówno DFA stanie końcowym, tak, że będzie P _[2,4], ponieważ zawiera on stan końcowy zarówno DFA.
Jeśli wziąć lub zarówno DFA stan końcowy będzie P _[0,4] Q _[2,3] Q _[1,4] Q _{[2, 4]}.
Tabela przejściowa chciałaby tego po dodaniu stanu końcowego.

Etap 4:
nazwy wszystkich stanowi Q _{[i, j]}
P _[0,3] Q
P _{[1 3]} do Q
Q _{[0,4]Q
P [2,3] Q
P [1,4] Q
P [2,4] Q
Ostateczna wersja DFA będzie wyglądać jak poniżej.}