Wie finden Sie die Kreuzung von zwei NFA
In DFA können wir die Schnittmenge der beiden Automaten, indem Sie die Kreuzprodukt der Zustände der beiden Automaten und das akzeptieren jene Staaten, die die Annahme sowohl in der ursprünglichen Automaten.
Union erfolgt in ähnlicher Weise. Wie auch immer, ich kann zwar union im NFA einfach mit epsilon-übergang wie mache ich Ihr Schnittpunkt?
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie das Kreuz-Produkt-Konstruktion auf NFAs nur, als würden Sie DFAs. Die einzigen änderungen sind, wie würden Sie behandeln ε-übergänge. Speziell, für jeden Zustand (qi, rj) in die cross-product-Automat, fügen Sie ein ε-übergang von diesem Zustand zu jedem paar von Zuständen (qk, rj) wo gibt es einen ε-übergang in die erste Maschine von fi qk und jedes paar von Zuständen (qi, rk), wo es einen ε-übergang in die zweite Maschine von rj rk.
Alternativ können Sie konvertieren Sie stets die NFAs in DFAs und berechnen Sie das Kreuzprodukt dieser DFAs.
Hoffe, das hilft!
es ist ein großer Fehler in der templatetypedef 's Antwort .
des Produkt-Automaten von L1 und L2, die NFAs :
neuen Mitgliedstaaten Q = Produkt der Zustände von L1 und L2 .
jetzt die übergangs-Funktion :
einen ist ein symbol der Vereinigung der beiden Automaten Alphabete
delta (q_1,q_2) , a) = delta_L1(q_1 , a) X delta_L2(q_2 , a)
das heißt, Sie sollten multiplizieren Sie die Menge, die die resualt von delta_L1(q_1 , a) mit dem Satz, dass die Ergebnisse von delta_L2(q_1 , a).
das problem in der templatetypedef die Antwort ist, dass die Produkt-Ergebnis (qk ,rk) wird nicht erwähnt .
Können wir auch De-Morgan-Gesetze: Ein Schnittpunkt B = (A' U B')'
Einnahme der union für die Komplimente zu den beiden NFA ' s ist vergleichsweise einfacher, vor allem, wenn Sie verwendet werden, um die epsilon-Methode der union.
Wahrscheinlich eine späte Antwort, aber da hatte ich das similair problem heute fühlte ich mich wie zu teilen. Erkennen die Bedeutung der ersten Kreuzung. Hier bedeutet es, dass Sie die Zeichenfolge e, e akzeptiert werden sollten, die von beiden Automaten.
Betrachten die folgenden Automaten:
Intiuitivly m = m1 ∩ m2 ist der Automat akzeptiert die Zeichenfolgen, die sowohl die " 11 " und " 00 " als substring. Die Idee ist, zu simulieren, beide Automaten gleichzeitig.
Let ' s nun formal definieren Sie den Schnittpunkt.
m = (Q, Σ, Δ, q0, F)
Beginnen wir mit der Definition der Mitgliedstaaten für m das ist, wie oben erwähnt, die carthesian Produkt der Zustände in m1 und m2. Also, wenn wir a1, a2 als Beschriftungen für die Staaten in m1, und b1, b2 die Staaten in m2, Q besteht aus folgenden Staaten: a1b1, a2b1, a1b2, a2b2. Der Sinn dahinter ist zu verfolgen, wo, wo sind in beiden m1 und m2.
Σ wahrscheinlich bleibt die gleiche, jedoch in einigen Fällen unterscheiden Sie sich und nehmen wir nur die Vereinigung der Alphabete in m1 und m2.
q0 ist jetzt der Zustand in Q, die sowohl den start-Zustand des m1 und der start-Zustand von m2. (a1b1, um ein Beispiel zu geben.)
F Status enthält s, WENN, und nur WENN die beiden genannten Staaten in s akzeptieren Staaten von m1, m2 bzw.
Letzte, aber nicht zuletzt Δ; wir definieren delta wieder in Bezug auf die carthesian Produkt, wie folgt: Δ(a1b1, E) = Δ(m1)(a1, E) x Δ(m2)(b1, E) als auch mentoined in einem der oben genannten Antworten, wenn ich mich nicht Irre. Die intuitive Idee dahinter ist, nur reißen a1b1 auseinander und betrachten die Mitgliedstaaten a1 und b1 in Ihrer ursprünglichen Automaten. Jetzt haben wir "Durchlaufen" jeden möglichen Rand, können wählen Sie E zum Beispiel, und sehen, wohin es uns bringt, in den ursprünglichen Automaten. Nach, dass wir kleben diese Ergebnisse zusammen mit den carthesian Produkt. Wenn (a1, E) vorhanden ist, in m1, aber nicht Δ(b1, E) in m2 wird die Schneide nicht vorhanden in m, sonst werden wir eine Art von union Bau.
Alternative zu der Konstruktion des Produkt-Automaten ist, dass mehr komplizierte Kriterien für die Annahme. Normalerweise ein NFA akzeptiert einen Eingabestring, wenn es erreicht hat, eine aus einer Reihe von akzeptierenden endzuständen. Das kann erweitert werden, um Boolesche Kombinationen von Staaten. Insbesondere konstruieren Sie den Automaten für die Kreuzung, wie Sie auch für die union, aber betrachten Sie den resultierenden Automaten zum akzeptieren einer Eingabe-Zeichenfolge nur, wenn es (was entspricht) die Annahme der Endstand in beiden Automaten.