Da Sie das Eingabeformat nicht angegeben haben, gehe ich davon aus, dass 0 der Anfangszustand ist. Alle Ganzzahlen, die in der zweiten Spalte, aber nicht in der ersten Spalte erscheinen, akzeptieren Zustände (3 für T1 und 2 für T2). und jede Zeile ist ein Element der Übergangsbeziehung, die den vorherigen Zustand, den nächsten Zustand, den Eingangsbuchstaben und den Ausgangsbuchstaben angibt.
Jede Operation auf FSTs muss eine neue FST erzeugen, also benötigen wir Zustände, ein Eingangs-Alphabet, ein Ausgangs-Alphabet, Anfangszustände, Endzustände und eine Übergangsbeziehung (die Spezifikationen der FSTs A, B und W sind unten) in dieser Reihenfolge gegeben). Nehmen wir an unsere FST sind:
A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)
und wollen wir
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
Hinweis finden, dass wir nicht brauchen, die Alphabete von W zu bestimmen; Die Definition der Komposition macht das.
Stellen Sie sich vor, dass A und B in Reihe laufen, wobei das A-Ausgangsband als Eingangsband von B zugeführt wird. Der Zustand der kombinierten FST ist einfach die kombinierten Zustände von A und B. Mit anderen Worten, die Zustände der Zusammensetzung sind im Kreuzprodukt der Zustände der einzelnen FSTs.
R = Q × P
In Ihrem Beispiel würden die Zustände der W Paare von ganzen Zahlen sein:
R = {(0,0), (0,1), ... (3, 2)}
obwohl wir diese neu nummerieren könnten und erhalten (zum Beispiel):
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
ähnlich Anfang und akzeptierende Zustände der zusammengesetzten FST sind die Kreuzprodukte derjenigen in der Komponente FSTs. Insbesondere akzeptiert R eine Zeichenkette iff A und B akzeptieren beide die Zeichenkette.
R0 = Q0 × P0
RF = QF × PF
Im Beispiel R 0 = {00} und R F = {32}.
Es bleibt nur noch die Übergangsbeziehung ω zu bestimmen. Kombinieren Sie dazu jede Übergangsregel für A mit jeder eventuell anzuwendenden Übergangsregel für B. Das heißt, kombinieren Sie jede Übergangsregel von A (qi, σ) → (qj, γ) mit jeder Regel von B, die ein "γ" als Eingabezeichen hat.
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
In dem Beispiel bedeutet dies kombinieren (z.B.) 0 1 a : b von T1 mit 0 1 b : a und 1 2 b : a von T2 erhalten:
00 11 a : a
01 12 a : a
ähnlich Sie 0 2 b : b von T1 mit den gleichen 0 1 b : a und 1 2 b : a von T2, 0 0 a : a von T1 mit 1 1 a : d und 1 2 a : c von T2 & c kombinieren würden.
Beachten Sie, dass Sie möglicherweise unerreichbare Zustände (die nie als "nächsten" Zustand erscheinen) und Übergänge, die niemals auftreten werden (solche aus unerreichbaren Zuständen). Als Optimierungsschritt können Sie diese Zustände und Übergänge entfernen. Wenn Sie sie jedoch zurücklassen, beeinträchtigt dies die Richtigkeit der Konstruktion nicht; es ist einfach eine Optimierung.