Die Kombination von deterministischen endlichen Automaten

Ich bin wirklich neu für dieses Zeug, so dass ich entschuldige mich für die noobishness hier.

konstruieren Deterministic Finite Automaton DFA erkennt die folgende Sprache:

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

Automatisieren für jeden Teil dieser (at least 2 a's, odd # of b's) sind einfach zu machen getrennt... Kann mir jemand bitte erklären, wie eine systematische Art und Weise zu kombinieren, Sie in ein? Danke.

InformationsquelleAutor Haskell | 2013-02-03

15

Können Sie folgende einfache Schritte zu konstruieren, kombiniert DFA.

Lassen Σ = {a₁ , a₂ , ...,_k }.

1. Schritt: Design DFA für beide Sprachen und deren Zustand Q₀, Q₁, ...

2. Schritt : Benennen Sie jeden Staat in beiden DFA eindeutig, d.h. benennen Sie alle Zustände im DFA-Q₀, Q₁, Q₂, Q₃ , ... vorausgesetzt, Sie haben begonnen, mit subskript 0; das bedeutet, dass keiner der Staat würde gleichen Namen.

3. Schritt: Konstrukt transition-Tabelle(δ) mit den folgenden Schritten

   3a. Start-Zustand des kombinierten DFA:

      Nehmen, starten Zustand des DFAs(DFA1 und DFA2), und benennen Sie Sie als F_{[ i , j ]}, wobei i und j der index des start-Zustand der DFA1 und DFA2 sind; d.h. Q_i start-Zustand des 1. DFA und F_j ist der Startzustand des 2. DFA und mark Q_{[i , j]} als start-Zustand des kombinierten DFA.

   3b. Karte Zustand des DFAs als

           wenn δ(Q_i,a_k) = F_p1 und δ(Q_j,a_k) = F_p2 , wo Q_p1 gehört zu DFA1 und F_p2 gehört zu DFA2 dann δ(Q_{[ i , j ]} , a_k) = F_[p1,p2]

   3c. füllen Sie die gesamte Tabelle, während es alle Q_[i,j] übrigen in transition-Tabelle.

   3d. Endzustand des kombinierten DFA:

      Für AND Fall Endzustand wäre für alle F_{[i , j]}, wobei Q_i und F_j Endzustand der DFA1 und DFA2 bzw.

      Für OR Fall Endzustand wäre für alle F_{[i , j]}, wobei entweder Q_i oder F_j ist der Letzte Stand der DFA1 und DFA2.

4. Schritt:
Benennen Sie alle Q_{[i, j]} - (einmalig) und zeichnen DFA dies wird Ihr Ergebnis.

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

DFA für ungerade Anzahl von b ' s .

DFA-mindestens 2 a ' s.

Schritt 2:

Benennen Sie die stae der DFA1

Step3(a,b,c):

Gebaut übergang Tabelle wird als.

Step3d:

Da haben wir zu nehmen, UND die beiden DFA-so Endzustand wäre Q_[2,4] , da es enthält die endgültigen Zustand des DFA .

, Wenn wir haben, zu nehmen ODER von beiden DFA-der Letzte Staat wäre Q_[0,4],Q_[2,3],Q_[1,4],Q_[2,4] .

Übergangs-Tabelle möchte diese nach dem hinzufügen der definitiven Zustand .

Schritt 4:

Benennen Sie alle Zustände Q_[i,j]

Q_[0,3] F₀

Q_[1,3] F₂

Q_[0,4] F₁

Q_[2,3] F₄

Q_[1,4] F₃

Q_[2,4] F₅

So endgültig DFA würde Aussehen wie unten .

würdest du auch erklären, was ist die Wissenschaft dahinter? was ist regex?

InformationsquelleAutor sonus21
1

Die Sprache L wo a sind mindestens zwei und b sind ungerade, ist eine reguläre Sprache. Seine DFA ist wie folgt:

In diesem DFA ich haben zusammen zwei DFSs konzeptionell!
```
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)
```
_{Der DFA ist auch symptomatisch und einfach so, glaube ich, nicht nötig, dass Wort, dass, wie beide miteinander zu kombinieren DFAs}

Zu ziehen, DFA Sie immer den überblick behalten, wie viele bs wurde kommen entweder sogar oder seltsam ist. States 0, 2 and 4 bedeutet, dass auch die Anzahl der b wurde kommen. So können Sie teilen Sie diesen DFA in zwei Teile vertikal wo unten die Staaten auf, auch bs und Ober-Staaten an den ungeraden.

Auch String wird akzeptiert, wenn ungerade b daher Endzustand sollten in einem Staat im oberen Teil.

nicht nur die Anzahl der bs Zustand, aber a sein sollte mindestens 2. So können Sie teilen diese DFA-horizontal in drei Teile, in denen die Anzahl der as 0 state-0 and 1, as sind eine auf state-2 and 3 und as 2 state-4 and 5. Nach den ersten zwei as beliebige Anzahl von as erlauben, in string, so gibt es self-loop auf Staatliche q4 und q5.

_{Anzahl der Staat ist sechs, weil, Zustand 2 für ungerade sogar b und ein s hould atleast 2 also 3 Zustände a=0, a=1, a=2, also 2*3 = 6}

InformationsquelleAutor Grijesh Chauhan
1

Es ist getan mit dem Produkt der beiden Automaten.

Ich bin immer noch stecken. Kann jemand erklären, diese mit Worten?
Vielleicht möchten Sie auch einen Blick auf jflap.org
Ich baute die beiden Automaten, die kann ich in jflap... wie kann ich Sie kombinieren, in ein?
Es gibt tutorials auf der website: jflap.org/tutorial

InformationsquelleAutor Dan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.