Wie kann man die Schnittpunktkonstruktion zur Bildung eines DFA verwenden?

Question

Ich bin dabei, eine Hausaufgabe für meine Theorie der Berechnung Klasse und bin ein bisschen verwirrt, wie 2 DFAs zu kombinieren. Im Buch steht, dass man dazu die "Schnittpunktkonstruktion" verwendet, aber ich bin mir nicht sicher, was das ist. Hier sind 2 Beispiele:

Answer 1

Die Idee ist ziemlich einfach, obwohl ich verstehe, woher die Verwirrung kommt. I

Ein DFA ist ein 5-Tupel (E, Q, q0, A, f), wobei

1. E ist das Eingabealphabet, eine nicht leere endliche Menge von Symbolen
2. Q ist die Menge der Zustände, nicht leer und endlich
3. q0 ist der Startzustand, ein Element von Q
4. A ist die Menge der akzeptierenden oder endgültigen Zustände, eine Teilmenge von Q
5. f ist die Übergangsfunktion, die Paare von Q x E nach Q

Angenommen, wir haben zwei Maschinen M' = (E', Q', q0', A', f') und M'' = (E'', Q'', q0'', A'', f''). Um die Diskussion zu erleichtern, nehmen wir E' = E'' an. Wir werden nun M''' so konstruieren, dass L(M''') = L(M') L(M'') schneidet (oder vereint oder unterscheidet).

1. Man nehme E''' = E'' = E'
2. Man nehme Q''' = Q' x Q''
3. Man nehme q0''' = (q0', q0'')
4. Man nehme A''' = (x, y), wobei x in A' und y in A'' ist (für Vereinigung, x in A' oder y in A''; für Differenz, x in A' aber nicht y in A'').
5. Man nehme f'''((x, y), e) = (f'(x, e), f''(y, e)).

Das war's! Betrachten wir nun zwei Maschinen: eine, die a^2n akzeptiert, und eine, die a^3n akzeptiert (die Schnittmenge sollte eine Maschine sein, die a^6n akzeptiert... richtig?).

Für M', haben wir...

1. E' = {a}
2. Q' = {s0, s1}
3. q0' = s0
4. A' = {s0}
5. f'(s0, a) = s1, f'(s1, a) = s0

Für M'', haben wir...

1. E'' = {a}
2. Q'' = {t0, t1, t2}
3. q0'' = t0
4. A'' = {t0}
5. f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0

Für M''' erhalten wir...

1. E''' = {a}
2. Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
3. q0''' = (s0, t0)
4. A''' = {(s0, t0)} für Schnittmenge, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} für Vereinigung, {(s0, t1), (s0, t2)} für Differenz.
5. f'''((s0, t0), a) = (s1, t1), f'''((s1, t1), a) = (s0, t2), f'''((s0, t2), a) = (s1, t0), f'''((s1, t0), a) = (s0, t1), f'''((s0, t1), a) = (s1, t2), f''''((s1, t2), a) = (s0, t0).

Und los geht's! Bitte lassen Sie es mich wissen, wenn dies einer Klarstellung bedarf.

Answer 2

Diese sind: {s{a,b,c}:auf jedes a in s folgt unmittelbar ein b} {s{a,b,c}:auf jedes a in s folgt unmittelbar ein b} und {s{a,b,c}:jedem c in s geht unmittelbar ein b voraus}

Vor und vor einem anderen Automaten können Sie die Zustände "0" und "2" verbinden.

und das müssen Sie beibehalten ...

Es gibt einen präzisen Weg, um Automaten für die Kreuzung von Sprachen zu erstellen. AA und BB seien die Eingabeautomaten. Die Fälle des neuen Automaten sind alle Paare von Zuständen von AA und BB, d.h. SAB=SA×SBSAB=SA×SB, der Anfangszustand ist iAB=iA,iBiAB=iA,iB, wobei iAiA und iBiB die Anfangszustände von AA und BB sind, und FAB=FA×FBFAB=FA×FB, wobei FXFX die Menge der akzeptierenden Zustände von XX bezeichnet. Schließlich ist die Übergangsfunktion ABAB für jeden Buchstaben und die Zustände p1,p2SAp1,p2SA, q1,q2SBq1,q2SB wie folgt definiert:

p1,q1AB p2,q2 iff p1A p2undq1B q2 p1,q1AB p2,q2 iff p1A p2undq1B q2 Bitte beachten Sie, dass ein solcher Automat in der Regel nicht minimal ist (z.B. könnte die Schnittmenge einfach eine leere Sprache sein). Außerdem kann es nützlich sein (ist aber nicht notwendig), Eingabeautomaten minimal zu machen, da die Ausgabe quadratisch ist. // Verweis: math.stackexchange.com Viel Spaß beim Kodieren ...